×

Graphs with the circuit cover property. (English) Zbl 0810.05043

Authors’ summary: A circuit cover of an edge-weighted graph \((G,p)\) is a multiset of circuits in \(G\) such that every edge \(e\) is contained in exactly \(p(e)\) circuits in the multiset. A nonnegative integer valued weight vector \(p\) is admissible if the total weight of any edge-cut is even, and no edge has more than half the total weight of any edge-cut containing it. A graph \(G\) has the circuit cover property if \((G,p)\) has a circuit cover for every admissible weight vector \(p\). We prove that a graph has the circuit cover property if and only if it contains no subgraph homeomorphic to Petersen’s graph. In particular, every 2-edge- connected graph with no subgraph homeomorphic to Petersen’s graph has a cycle double cover.

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon and M. Tarsi, Covering multigraphs by simple circuits, SIAM J. Algebraic Discrete Methods 6 (1985), no. 3, 345 – 350. · Zbl 0581.05046 · doi:10.1137/0606035
[2] Brian Alspach and Cun Quan Zhang, Cycle covers of cubic multigraphs, Discrete Math. 111 (1993), no. 1-3, 11 – 17. Graph theory and combinatorics (Marseille-Luminy, 1990). · Zbl 0789.05075 · doi:10.1016/0012-365X(93)90135-G
[3] Dan Archdeacon, Face colorings of embedded graphs, J. Graph Theory 8 (1984), no. 3, 387 – 398. · Zbl 0545.05036 · doi:10.1002/jgt.3190080307
[4] Jean-Claude Bermond, Bill Jackson, and François Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B 35 (1983), no. 3, 297 – 308. · Zbl 0559.05037 · doi:10.1016/0095-8956(83)90056-4
[5] J. A. Bondy, Small cycle double covers of graphs, Cycles and rays (Montreal, PQ, 1987) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301, Kluwer Acad. Publ., Dordrecht, 1990, pp. 21 – 40.
[6] U. A. Celmins, On cubic graphs that do not have an edge 3-coloring, Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984.
[7] Paul A. Catlin, Double cycle covers and the Petersen graph, J. Graph Theory 13 (1989), no. 4, 465 – 483. · Zbl 0713.05040 · doi:10.1002/jgt.3190130408
[8] W. Cook, J. Fonlupt, and A. Schrijver, An integer analogue of Carathéodory’s theorem, J. Combin. Theory Ser. B 40 (1986), no. 1, 63 – 70. · Zbl 0589.52005 · doi:10.1016/0095-8956(86)90064-X
[9] Jack Edmonds and Ellis L. Johnson, Matching, Euler tours and the Chinese postman, Math. Programming 5 (1973), 88 – 124. · Zbl 0281.90073 · doi:10.1007/BF01580113
[10] M. N. Ellingham, Petersen subdivisions in some regular graphs, Proceedings of the fifteenth southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), 1984, pp. 33 – 40. · Zbl 0558.05040
[11] Genghua Fan, Covering weighted graphs by even subgraphs, J. Combin. Theory Ser. B 49 (1990), no. 1, 137 – 141. · Zbl 0717.05066 · doi:10.1016/0095-8956(90)90067-A
[12] Genghua Fan, Integer flows and cycle covers, J. Combin. Theory Ser. B 54 (1992), no. 1, 113 – 122. · Zbl 0776.05084 · doi:10.1016/0095-8956(92)90069-A
[13] Herbert Fleischner, Eulersche Linien und Kreisüberdeckungen, die vorgegebene Durchgänge in den Kanten vermeiden, J. Combin. Theory Ser. B 29 (1980), no. 2, 145 – 167 (German). · Zbl 0438.05041 · doi:10.1016/0095-8956(80)90077-5
[14] Herbert Fleischner and András Frank, On circuit decomposition of planar Eulerian graphs, J. Combin. Theory Ser. B 50 (1990), no. 2, 245 – 253. · Zbl 0769.05074 · doi:10.1016/0095-8956(90)90080-J
[15] L. R. Ford Jr. and D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton, N.J., 1962. · Zbl 0106.34802
[16] X. Fu and L. A. Goddyn, Matroids with the circuit cover property (in preparation). · Zbl 0920.05016
[17] D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168 – 194. · Zbl 0254.90054 · doi:10.1007/BF01584085
[18] Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. · Zbl 0411.68039
[19] Luis A. Goddyn, Cycle double covers of graphs with Hamilton paths, J. Combin. Theory Ser. B 46 (1989), no. 2, 253 – 254. · Zbl 0618.05033 · doi:10.1016/0095-8956(89)90048-8
[20] -, Cycle covers of graphs, Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1988.
[21] Mei Gu Guan and Herbert Fleischner, On the minimum weighted cycle covering problem for planar graphs, Ars Combin. 20 (1985), 61 – 67. · Zbl 0599.05035
[22] Gary Haggard, Unsolved Problems: Loops in Duals, Amer. Math. Monthly 87 (1980), no. 8, 654 – 656. · Zbl 0444.05038 · doi:10.2307/2320955
[23] Alon Itai and Michael Rodeh, Covering a graph by circuits, Automata, languages and programming (Fifth Internat. Colloq., Udine, 1978), Lecture Notes in Comput. Sci., vol. 62, Springer, Berlin-New York, 1978, pp. 289 – 299. · Zbl 0386.05047
[24] Bill Jackson, Shortest circuit covers and postman tours in graphs with a nowhere zero 4-flow, SIAM J. Comput. 19 (1990), no. 4, 659 – 665. · Zbl 0697.68040 · doi:10.1137/0219044
[25] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), no. 2, 205 – 216. · Zbl 0422.05028 · doi:10.1016/0095-8956(79)90057-1
[26] François Jaeger, A survey of the cycle double cover conjecture, Cycles in graphs (Burnaby, B.C., 1982) North-Holland Math. Stud., vol. 115, North-Holland, Amsterdam, 1985, pp. 1 – 12. · doi:10.1016/S0304-0208(08)72993-1
[27] Ury Jamshy and Michael Tarsi, Cycle covering of binary matroids, J. Combin. Theory Ser. B 46 (1989), no. 2, 154 – 161. · Zbl 0776.05066 · doi:10.1016/0095-8956(89)90041-5
[28] Ury Jamshy, André Raspaud, and Michael Tarsi, Short circuit covers for regular matroids with a nowhere zero 5-flow, J. Combin. Theory Ser. B 43 (1987), no. 3, 354 – 357. · Zbl 0659.05038 · doi:10.1016/0095-8956(87)90011-6
[29] Ury Jamshy and Michael Tarsi, Short cycle covers and the cycle double cover conjecture, J. Combin. Theory Ser. B 56 (1992), no. 2, 197 – 204. · Zbl 0776.05066 · doi:10.1016/0095-8956(92)90018-S
[30] Eugene L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York-Montreal, Que.-London, 1976. · Zbl 0413.90040
[31] Charles H. C. Little and Richard D. Ringeisen, On the strong graph embedding conjecture, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congress. Numer., XXI, Utilitas Math., Winnipeg, Man., 1978, pp. 479 – 487. · Zbl 0412.05038
[32] K. R. Matthews, On the Eulericity of a graph, J. Graph Theory 2 (1978), no. 2, 143 – 148. · Zbl 0407.05062 · doi:10.1002/jgt.3190020207
[33] Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. · Zbl 0665.90063
[34] P. D. Seymour, Sums of circuits, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) Academic Press, New York-London, 1979, pp. 341 – 355.
[35] P. D. Seymour, Matroids and multicommodity flows, European J. Combin. 2 (1981), no. 3, 257 – 290. · Zbl 0479.05023 · doi:10.1016/S0195-6698(81)80033-9
[36] P. D. Seymour, Even circuits in planar graphs, J. Combin. Theory Ser. B 31 (1981), no. 3, 327 – 338. · Zbl 0493.05041 · doi:10.1016/0095-8956(81)90034-4
[37] P. D. Seymour and N. Roberson, Graph Minors. XIII: The disjoint paths problem (submitted). · Zbl 0823.05038
[38] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8 (1973), 367 – 387. · Zbl 0249.05111 · doi:10.1017/S0004972700042660
[39] Michael Tarsi, Nowhere zero flow and circuit covering in regular matroids, J. Combin. Theory Ser. B 39 (1985), no. 3, 346 – 352. · Zbl 0584.05018 · doi:10.1016/0095-8956(85)90059-0
[40] Michael Tarsi, Semiduality and the cycle double cover conjecture, J. Combin. Theory Ser. B 41 (1986), no. 3, 332 – 340. · Zbl 0607.05019 · doi:10.1016/0095-8956(86)90054-7
[41] W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. (2) 51 (1949), 474 – 483. · Zbl 0033.30803 · doi:10.1112/plms/s2-51.6.474
[42] D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. · Zbl 0343.05002
[43] D. H. Younger, Integer flows, J. Graph Theory 7 (1983), no. 3, 349 – 357. · Zbl 0515.05057 · doi:10.1002/jgt.3190070307
[44] Bohdan Zelinka, On a problem of P. Vestergaard concerning circuits in graphs, Czechoslovak Math. J. 37(112) (1987), no. 2, 318 – 319. · Zbl 0676.05064
[45] Cun Quan Zhang, Minimum cycle coverings and integer flows, J. Graph Theory 14 (1990), no. 5, 537 – 546. · Zbl 0729.05041 · doi:10.1002/jgt.3190140504
[46] -, On compatible cycle decompositions of eulerian graphs, preprint.
[47] -, On even cycle decompositions of eulerian graphs, preprint.
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.