Namespaces
Variants
Actions

Graph homeomorphism

From Encyclopedia of Mathematics
Revision as of 17:16, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

An equivalence relation on the set of graphs, characterizing their geometric properties. The notion of a graph homeomorphism is defined as follows. Subdivision of an edge of a graph is an operation involving the addition of a new vertex , the removal of , and the addition of two new edges and . Geometrically, this operation consists in addition of some (interior) point on the line ; this point then becomes a new vertex. A graph is called a subdivision of a graph if it can be obtained from by repeating the operation of edge subdivision several times. Two graphs and are said to be homeomorphic if they have isomorphic subdivisions (cf. Graph isomorphism).

How to Cite This Entry:
Graph homeomorphism. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_homeomorphism&oldid=32339
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article