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) --&gt; {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. - ELETTRONICO. - (2002), pp. 1-6.

### Cycle Cover Property and CPP=SCC Property are not Equivalent

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Cycle Cover Property and CPP=SCC Property are not Equivalent / Rizzi, Romeo. - ELETTRONICO. - (2002), pp. 1-6.
Rizzi, Romeo
File in questo prodotto:
File
103.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Dimensione 240.75 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11572/358737`