Definition:Subdivision (Graph Theory)

From ProofWiki
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$.


Example

This:

Example subdivision graph.png

is a graph subdivision of this:

ExampleOfGraph.png

obtained by performing:

an edge subdivision $\left\{ {A, E}\right\}$

and:

an edge subdivision $\left\{ {C, D}\right\}$.


Sources