Definition:Subdivision (Graph Theory)
Jump to navigation
Jump to search
This page is about Subdivision in the context of Graph Theory. For other uses, see Subdivision.
Definition
Let $G = \struct {V, E}$ be a graph.
Edge Subdivision
The edge subdivision operation for an edge $\set {u, v} \in E$ is the deletion of $\set {u, v}$ from $G$ and the addition of two edges $\set {u, w}$ and $\set {w, v}$ along with the new vertex $w$.
This operation generates a new graph $H$:
- $H = \struct {V \cup \set w, \paren {E \setminus \set {u, v} } \cup \set {\set {u, w}, \set {w, v} } }$
Graph Subdivision
A graph which has been derived from $G$ by a sequence of edge subdivision operations is called a subdivision of $G$.
Examples
Arbitrary Example
This:
is a graph subdivision of this:
obtained by performing:
- an edge subdivision $\set {A, E}$
and:
- an edge subdivision $\set {C, D}$.
Also see
- Results about subdivisions in the context of Graph Theory can be found here.
Sources
- 1998: O. Melnikov, V. Sarvanov, R. Tyshkevich, V. Yemelichev and I. Zverovich: Exercises in Graph Theory: Section $1.2$
- 2008: J.A. Bondy and U.S.R. Murty: Graph Theory: Section $10.1$