Definition:Subdivision (Graph Theory)/Edge
< Definition:Subdivision (Graph Theory)(Redirected from Definition:Edge Subdivision)
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be a graph.
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} } }$
Also known as
This operation is also known as elementary subdivision.
Also see
- Definition:Graph Subdivision: a graph obtained from another by a sequence of edge subdivisions.
- 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$
- 1999: Kenneth H. Rosen: Discrete Mathematics and Its Applications (4th ed.): Section $7.7$
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): subdivision (of a graph)