Lecture Notes in Computer Science, 2007, Volume 4381/2007, 59-69, DOI: 10.1007/978-3-540-70666-3_7

Impossibility of Transformation of Vertex Labeled Simple Graphs Preserving the Cut-Size Order

Hiro Ito

View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document