Definition:Vertex Deletion
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be an (undirected) graph.
Let $W \subseteq V$ be a set of vertices of $G$.
Then the graph obtained by deleting $W$ from $G$, denoted by $G - W$, is the subgraph induced by $V \setminus W$.
Alternatively:
- $G - W = \struct {V \setminus W, \set {e \in E : e \cap W = \O} }$
Informally, $G - W$ is the graph obtained from $G$ by removing all vertices in $W$ and all edges incident to those vertices.
If $W$ is a singleton such that $W = \set v$, then $G - W$ may be expressed $G - v$.
Also see
- Definition:Vertex Cut, where the vertex deletion separates the graph into disconnected components.
- Definition:Cut-Vertex, which is a singleton Vertex Cut.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.4$: Cut-Vertices and Bridges