graph homeomorphism
Let be a simple undirected graph.
A simple subdivision is the replacement of an edge
with a pair of edges ,
being a new vertex, i.e., .
The reverse operation of a simple subdivision
is an edge-contraction through a vertex of degree 2.
Two graphs , are homeomorphic
if can be transformed into
via a finite sequence of simple subdivisions
and edge-contractions through vertices of degree 2.
It is easy to see that graph homeomorphism is an equivalence relation
.
Equivalently, and are homeomorphic if there exists a third graph such that both and can be obtained from via a finite sequence of edge-contractions through vertices of degree 2.
If a graph has a subgraph
which is homeomorphic to a graph having no vertices of degree 2,
then is a minor of .
The vice versa is not true:
as a counterexample, the Petersen graph
has as a minor, but no subgraph homeomorphic to .
This happens because a graph homeomorphism
cannot change the number of vertices of degree :
since all the vertices of have degree 4
and all the vertices of the Petersen graph have degree 3,
no subgraph of the Petersen graph can be homeomorphic to .
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 |