Let G be an undirected graph. The Chinese Postman Problem (CPP) asks for a shortest postman tour in G, i.e. a closed walk using each edge at least once. The Shortest Cycle Cover Problem (SCC) asks for a family \C of circuits of G such that each edge is in some circuit of \C and the total length of all circuits in \C is as small as possible. Clearly, an optimal solution of CPP can not be greater than a solution of SCC. A graph G has the CPP=SCC property when the solutions to the two problems have the same value. Graph G is said to have the cycle cover property if for every Eulerian 1,2-weighting w: E(G) --> {1,2} there exists a family \C of circuits of G such that every edge e is in precisely w_e circuits of \C. The cycle cover property implies the CPP=SCC property. We give a counterexample to a conjecture of Zhang stating the equivalence of the cycle cover property and the CPP=SCC property for 3-connected graphs. This is also a counterexample to the stronger conjecture of Lai and Zhang, stating that every 3-connected graph with the CPP=SCC property has a nowhere-zero 4-flow. We actually obtain infinitely many cyclically 4-connected counterexamples to both conjectures.
Cycle cover property and CPP=SCC property are not equivalent
RIZZI, ROMEO
2002-01-01
Abstract
Let G be an undirected graph. The Chinese Postman Problem (CPP) asks for a shortest postman tour in G, i.e. a closed walk using each edge at least once. The Shortest Cycle Cover Problem (SCC) asks for a family \C of circuits of G such that each edge is in some circuit of \C and the total length of all circuits in \C is as small as possible. Clearly, an optimal solution of CPP can not be greater than a solution of SCC. A graph G has the CPP=SCC property when the solutions to the two problems have the same value. Graph G is said to have the cycle cover property if for every Eulerian 1,2-weighting w: E(G) --> {1,2} there exists a family \C of circuits of G such that every edge e is in precisely w_e circuits of \C. The cycle cover property implies the CPP=SCC property. We give a counterexample to a conjecture of Zhang stating the equivalence of the cycle cover property and the CPP=SCC property for 3-connected graphs. This is also a counterexample to the stronger conjecture of Lai and Zhang, stating that every 3-connected graph with the CPP=SCC property has a nowhere-zero 4-flow. We actually obtain infinitely many cyclically 4-connected counterexamples to both conjectures.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
