graph homeomorphism

Let G=(V,E) be a simple undirected graph. A simple subdivision is the replacement of an edge (x,y)E with a pair of edges (x,z),(z,y), z being a new vertex, i.e., zV. The reverse operationMathworldPlanetmath of a simple subdivision is an edge-contraction through a vertex of degree 2.

Two graphs G1, G2 are homeomorphic if G1 can be transformed into G2 via a finite sequencePlanetmathPlanetmath of simple subdivisions and edge-contractions through vertices of degree 2. It is easy to see that graph homeomorphism is an equivalence relationMathworldPlanetmath.

Equivalently, G1 and G2 are homeomorphic if there exists a third graph G3 such that both G1 and G2 can be obtained from G3 via a finite sequence of edge-contractions through vertices of degree 2.

If a graph G has a subgraphMathworldPlanetmath H which is homeomorphic to a graph G having no vertices of degree 2, then G is a minor of G. The vice versa is not true: as a counterexample, the Petersen graphMathworldPlanetmathPlanetmath has K5 as a minor, but no subgraph homeomorphic to K5. This happens because a graph homeomorphism cannot change the number of vertices of degree d2: since all the vertices of K5 have degree 4 and all the vertices of the Petersen graph have degree 3, no subgraph of the Petersen graph can be homeomorphic to K5.

Title graph homeomorphism
Canonical name GraphHomeomorphism
Date of creation 2013-03-22 18:02:02
Last modified on 2013-03-22 18:02:02
Owner Ziosilvio (18733)
Last modified by Ziosilvio (18733)
Numerical id 8
Author Ziosilvio (18733)
Entry type Definition
Classification msc 05C99
Defines simple subdivision