2007 | OriginalPaper | Buchkapitel
Impossibility of Transformation of Vertex Labeled Simple Graphs Preserving the Cut-Size Order
verfasst von : Hiro Ito
Erschienen in: Discrete Geometry, Combinatorics and Graph Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same number of vertices are known to be equivalent. From the equivalence,
G
precedes
G
′ in the order means that there is a sequence of cross-operations transforming
G
into
G
′. However, even if both graphs are simple, non-simple graphs may appear on the way of the transformation. If both graphs have the same number of edges, we conjecture that there is a sequence in which only simple graphs appear. But for graphs having different number of edges, there is a counter example. That is, there is a pair of simple graphs
G
and
G
′ such that
G
precedes
G
′ in the order and
G
can not be transformed into
G
′ by using only simple graphs. Thus we must introduce other operations than cross-operation for transforming them by using only simple graphs. Then we naturally reach to a question: is there a sufficient set of operations for this purpose? For this problem, this paper shows a negative result that there is no such finite set of operations.