Proofs of two minimum circuit cover conjectures. (English) Zbl 1024.05074
Summary: Let \(G\) be a 2-edge-connected graph with \(m\) edges and \(n\) vertices. The following two conjectures are proved in this paper. (i) The edges of \(G\) can be covered by circuits of total length at most \(m+n-1\). (ii) The vertices of \(G\) can be covered by circuits of total length at most \(2(n-1)\), where \(n\geq 2\).
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
Keywords:
2-edge-connected graphReferences:
| [1] | Alon, N.; Tarsi, M., Covering multigraphs by simple circuits, SIAM J. Algebraic Discrete Methods, 6, 345-350 (1985) · Zbl 0581.05046 |
| [2] | Alspach, B.; Goddyn, L.; Zhang, C. Q., Graphs with the circuit cover property, Trans. Amer. Math. Soc., 344, 131-154 (1994) · Zbl 0810.05043 |
| [3] | Bermond, J. C.; Jackson, B.; Jaeger, F., Shortest covering of graphs with cycles, J. Combin. Theory Ser. B, 35, 297-308 (1983) · Zbl 0559.05037 |
| [4] | Edmonds, L.; Johnson, E. L., Matching, Euler torus and the Chinese postman, Math. Programming, 5, 88-124 (1973) · Zbl 0281.90073 |
| [5] | Fan, G., Covering graphs by cycles, SIAM J. Discrete Math., 5, 491-496 (1992) · Zbl 0777.05087 |
| [6] | Fan, G., Extensions of flow theorems, J. Combin. Theory Ser. B, 69, 110-114 (1997) · Zbl 0873.05059 |
| [7] | Fan, G., Minimum cycle covers of graphs, J. Graph Theory, 25, 229-242 (1997) · Zbl 0872.05041 |
| [8] | Fraisse, P., Cycle covering in bridgeless graphs, J. Combin. Theory Ser. B, 39, 146-152 (1985) · Zbl 0583.05035 |
| [9] | Itai, A.; Lipton, R. J.; Papadimitriou, C. H.; Rodeh, M., Covering graphs with simple circuits, SIAM J. Comput., 10, 746-750 (1981) · Zbl 0468.68071 |
| [10] | Itai, A.; Rodeh, M., Covering a graph by circuits, Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, 62 (1978), Springer-Verlag: Springer-Verlag Berlin, p. 289-299 · Zbl 0386.05047 |
| [11] | Jackson, B., Shortest circuit covers and postman tours of graphs with a nowhere-zero 4-flow, SIAM J. Comput., 19, 659-665 (1990) · Zbl 0697.68040 |
| [12] | Jaeger, F., Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26, 205-216 (1979) · Zbl 0422.05028 |
| [13] | Seymour, P. D., Nowhere-zero 6-flows, J. Combin. Theory Ser. B, 30, 130-135 (1981) · Zbl 0474.05028 |
| [14] | Thomassen, C., MAT-Report (1994) |
| [15] | Tutte, W. T., A class of abelian groups, Can. J. Math., 8, 13-28 (1956) · Zbl 0070.02302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
