Subdivision graph

Subdivision graph of the complete graph K ₅ , which is created by subdividing all edges

A subdivision graph is graph theory , a graph , by edge subdivision was created from a different graph. Two graphs are called homeomorphic if they have subdivision graphs that are isomorphic . Subdivision graphs play an important role in Kuratowski's theorem and in the Hajós conjecture , among others .

Definitions

Subdivision graph

Edge before and after subdivision

Is an undirected graph , then is meant by a subdivision of an edge of the replacement of this edge by two new edges and that the two nodes and the distal edge with a new node connect. This creates a new graph with the new set of nodes ${\displaystyle G=(V,E)}$ ${\displaystyle e=\{u,v\}\in E}$ ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle w\notin V}$ ${\displaystyle G'=(V',E')}$

${\displaystyle V'=V\cup \{w\}}$

and the new set of edges

${\displaystyle E'=E\setminus \{e\}\cup \{e_{1},e_{2}\}}$,

where and are. A subdivision graph of a graph is now a graph that arises from it by (zero, one or more times) edge subdivision. ${\displaystyle e_{1}=\{u,w\}}$ ${\displaystyle e_{2}=\{w,v\}}$

Homeomorphism of graphs

Two graphs are called homeomorphic if there are subdivision graphs of these two graphs that are isomorphic to each other . The homeomorphic origin of a graph is the smallest graph that is homeomorphic to it. The homeomorphism origin of a graph can be determined by repeatedly removing nodes of degree two ( excluding loops ) and inserting an edge connecting the two neighboring nodes of the removed node. Two graphs are now homeomorphic if and only if their homeomorphism origins are isomorphic.

Examples

The following two graphs and are homeomorphic because they share the common subdivision graph . The homeomorphism origin of the two graphs is the graph . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle D}$

• 

  Graph A

• 

  Graph B

• 

  Common subdivision graph C

• 

  Homeomorphism Origin D

All circular graphs are also homeomorphic to one another with the graph as the homeomorphic origin. ${\displaystyle C_{n}}$ ${\displaystyle n\geq 2}$ ${\displaystyle C_{2}}$

use

Subdivision graphs play an important role in Kuratowski's theorem . According to this theorem, a finite graph is planar if and only if it does not contain a subgraph that has been created by subdividing the complete graph or the completely bipartite graph . They also serve to define topological minors . ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

See also

• Edge contraction

Web links

• Béla Bollobás: Subdivision . In: PlanetMath . (English)
• Ed Pegg, Jr .: Edge splitting . In: MathWorld (English).