Hiro Ito

In this talk every graph G has a real edge-weight function w_G and has the unique vertex set N={ 0, 1,..., n-1 }. We sometimes regard a graph as a complete graph, since no edge can be represented by zero weight. A simple graph is a graph with w_G(i)

{0,1} for all i

N.Three partial orders, cut-size order, length order, and operation order, defined between graphs are known to be equivalent[1,2].

Operation order.Let i,j,k,h

N be a pair of vertices such that i

h, j

i, k

j, or h

k; and let $\Delta >0$ be a positive real value. A cross operation X(i,j,k,h, \Delta) is removing $\Delta$ from the weights of edges $(i,j)$ and $(k,h)$ of G and adding $\Delta$ to the weights of edges (i,k) and (j,h) of G. X(i,j,k,h,1) is sometimes expressed as X(i,j,k,h) simply. For a pair of graphs G and G', that G precedes or equals to G' in operation order means that G can be transformed into G' by applying a sequence of cross operations (the sequence may be empty).

Cut-size order.A linear-cut C(i,j) (i < j and i,j

N) is a separation of the vertex set N into two successive vertex subsets [i,j-1] := { i,..., j-1 } and [j, i-1] := { j,..., n-1, 0,..., i-1 }. The size of linear-cut C(i,j) in G is the sum of weights of edges crossing the cut (edges (k,h) such that k

[i.j-1] and h

[j, i-1]). That G precedes or equals to G' in cut-size order means that for any linear-cut the cut size in G is less than or equal to the one in G'.
The definition of length order is omitted here.
From the equivalence of the orders, if G precedes or equals to G' in cut-size order (we denote it by G

G'), there is a sequence of cross-operations which transform G into G'. However, non-simple graph may be appeared even if both G and G' are simple graphs. In this problem, we have the following conjecture d_G(i) means the degree of vertex i in G).

Corollary 0.1 Let G and G' be two simple graphs with a node set $N$ and with $d_G(i) = d_{G'}(i)$ for all $i \in N$. Then $G \preceq G'$ if and only if there is a sequence of cross-operations such that it transforms G to G' and only simple graphs are appeared on the way of the transformation.

If the degree condition is deleted from the conjecture, it has a simple counter example (see, Fig.4) If we don't mind breaking the simpleness, there is a sequence X(0,0,1,3;0.5), X(2,2,3,1;0.5),X(1,1,2,0;0.5), X(3,3,0,2;0.5). However there is no efficient cross-operation that doesn't break the simpleness.
Thus we should to introduce other operations to complete transformations in general case. The example of Fig.4 can be solved if we introduce a new operation, a cross-square-operation, consisting of removing edges (i,k) and (j,h), and adding edges (i,j), (j,k), (k,h), and (h,i) for i j k h, j k h i, k h j j, or h i j k. Precisely, it may not be sufficient for general case. If we find another counter example, which can't be solved yet, then we should add another new operation.