Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Graphs with the circuit cover property


Authors: Brian Alspach, Luis Goddyn and Cun Quan Zhang
Journal: Trans. Amer. Math. Soc. 344 (1994), 131-154
MSC: Primary 05C38; Secondary 05C70
DOI: https://doi.org/10.1090/S0002-9947-1994-1181180-1
MathSciNet review: 1181180
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.


References [Enhancements On Off] (What's this?)

  • [Alo] N. Alon and M. Tarsi, Covering multigraphs by simple circuits, SIAM J. Algebraic Discrete Methods 6 (1985), 345-350. MR 791163 (86m:05067)
  • [Als] B. R. Alspach and C-Q. Zhang, Cycle coverings of cubic graphs, Discrete Math. 111 (1993), 11-17. MR 1210076 (94b:05142)
  • [Arc] D. Archdeacon, Face colorings of embedded graphs, J. Graph Theory 8 (1984), 387-398. MR 754919 (85j:05019)
  • [Ber] J. C. Bermond, B. Jackson, and F. Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B 35 (1983), 297-308. MR 735197 (86a:05078)
  • [Bon] J. A. Bondy, Small cycle double covers of graphs, Cycles and Rays (G. Hahn, G. Sabidussi, and R. Woodrow, eds.), Nato ASI Series C, vol. 301, Kluwer, Dordrecht and Boston, 1990, pp. 21-40. MR 1096982 (92e:05063)
  • [Cel] 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.
  • [Cat] P. Catlin, Double cycle covers and the Petersen graph, J. Graph Theory 13 (1989), 465-483. MR 1010580 (90g:05111)
  • [Coo] W. Cook, J. Fonloupt, and A. Schrijver, An integer analogue of Carathéodory's theorem, J. Combin. Theory Ser. B 40 (1986), 63-70. MR 830593 (87d:90111)
  • [Edm] J. Edmonds and E. L. Johnson, Matching, Euler-tours, and the Chinese postman, Math. Programming 5 (1973), 88-124. MR 0321801 (48:168)
  • [Ell] M. N. Ellingham, Petersen subdivisions in some regular graphs, Congr. Numer. 44 (1984), 33-40. MR 777527 (86e:05039)
  • [Fan1] G. Fan, Covering weighed graphs by even subgraphs, J. Combin. Theory Ser. B 49 (1990), 137-141. MR 1056823 (91e:05062)
  • [Fan2] -, Integer flows and cycle covers, J. Combin. Theory Ser. B 54 (1992), 113-122. MR 1142267 (92m:05147)
  • [Fle1] H. Fleischner, Eulersche Linien und Kreisüberdeckungen die vorgegebene Durchgange in den Kanten vermeiden, J. Combin. Theory Ser. B 2 (1980), 145-167. MR 586430 (82e:05094)
  • [Fle2] H. Fleischner and A. Frank, On circuit decompositions of planar Eulerian graphs, J. Combin. Theory Ser. B 50 (1990), 245-253. MR 1081229 (91i:05076)
  • [For] L. R. Ford and D. R. Fulkerson, Flows in networks, Princeton Univ. Press, Princeton, NJ, 1962. MR 0159700 (28:2917)
  • [Fu] X. Fu and L. A. Goddyn, Matroids with the circuit cover property (in preparation).
  • [Ful] D. R. Fulkerson, Blocking and antiblocking pairs of polyhedra, Mat. Programming 1 (1971), 168-194. MR 0294149 (45:3222)
  • [Gar] M. R. Gary and D. S. Jonsonson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979. MR 519066 (80g:68056)
  • [God1] L. A. Goddyn, Cycle double covers of graphs with Hamilton paths, J. Combin. Theory Ser. B 46 (1989), 253-254. MR 992996 (90d:05140)
  • [God2] -, Cycle covers of graphs, Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1988.
  • [Gua] M. Guan and H. Fleischner, On the minimum weight cycle covering problem for planar graphs, Ars Combin. 20 (1985), 61-68. MR 824849 (87f:05099)
  • [Hag] G. Haggard, Loops in duals, Amer. Math. Monthly 87 (1980), 654-656. MR 1539492
  • [Ita] A. Itai and M. Rodeh, Covering a graph by circuits, Automata, Languages, and Programming, Lecture Notes in Computer Science, no. 62, Springer, Berlin, 1978, pp. 289-299. MR 520849 (80i:05055)
  • [Jac] B. Jackson, Shortest circuit covers and postman tours in graphs with a nowhere zero 4-flow, SIAM J. Comput. 19 (1990), 659-665. MR 1053933 (92d:90026)
  • [Jae1] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), 205-216. MR 532588 (81j:05059)
  • [Jae2] -, A survey of the cycle double cover conjecture, Cycles in Graphs (B. R. Alspach and C. D. Godsil, eds.), Ann. Discrete Math., vol. 27, North-Holland, Amsterdam, 1985, pp. 1-12. MR 821502 (87b:05082)
  • [Jam1] U. Jamshy and M. Tarsi, Cycle covering of binary matroids, J. Combin. Theory Ser. B 46 (1989), 154-161. MR 992989 (90d:05069)
  • [Jam2] U. Jamshy, A. Raspaud, and M. Tarsi, Short circuit covers for regular matroids with a nowhere zero 5-flow, J. Combin. Theory Ser. B 42 (1987), 354-357. MR 916380 (88i:05053)
  • [Jam3] U. Jamshy and M. Tarsi, Short cycle covers and the cycle double cover conjecture, J. Combin. Theory Ser. B (submitted). MR 1186755 (94a:05119)
  • [Law] E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976. MR 0439106 (55:12005)
  • [Lit] C. Little and R. Ringeisen, On the strong graph embedding conjecture, Proc. Ninth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, 1978, pp. 479-487. MR 527973 (81f:05067)
  • [Mat] K. R. Matthews, On the Eulericity of a graph, J. Combin. Theory Ser. B 2 (1978), 143-148. MR 0491361 (58:10619)
  • [Sch] A. Schrijver, Theory of linear and integer programming, Wiley, New York, 1986, pp. 310-312. MR 874114 (88m:90090)
  • [Sey1] P. D. Seymour, Sums of circuits, Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.), Academic Press, New York, 1979, pp. 341-355. MR 538060 (81b:05068)
  • [Sey2] -, Matroids and multicommodity flows, Europ. J. Combin. 2 (1981), 257-290. MR 633121 (82m:05030)
  • [Sey3] -, Even circuits in planar graphs, J. Combin. Theory Ser. B 31 (1981), 327-338. MR 638288 (82m:05061)
  • [Sey4] P. D. Seymour and N. Roberson, Graph Minors. XIII: The disjoint paths problem (submitted).
  • [Sze] G. Szekeres, Polyhedral decompositions of cubic graphs, J. Austral. Math. Soc. 8 (1973), 367-387. MR 0325438 (48:3785)
  • [Tar1] M. Tarsi, Nowhere zero flows and circuit covering in regular matroids, J. Combin. Theory Ser. B 39 (1985), 346-352. MR 815401 (87a:05049)
  • [Tar2] -, Semi-duality and the cycle double cover conjecture, J. Combin. Theory Ser. B 41 (1986), 332-340. MR 864580 (87m:05060)
  • [Tut] W. T. Tuttle, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. (2) 51 (1950), 474-483. MR 0029495 (10:616b)
  • [Wel] D. Welsh, Matroid theory, Academic Press, San Francisco, 1976. MR 0427112 (55:148)
  • [You] D. H. Younger, Integer flows, J. Graph Theory 7 (1983), 349-357. MR 710909 (85d:05223)
  • [Zel] B. Zelinka, On a problem of P. Vestergaard concerning circuits in graphs, Czechoslovak Math. J. 37 (1987), 318-319. MR 882603 (88c:05077)
  • [Zha1] Cun-Quan Zhang, Minimal cycle coverings and integer flows, J. Graph Theory 14 (1990), 537-546. MR 1073094 (91j:05067)
  • [Zha2] -, On compatible cycle decompositions of eulerian graphs, preprint.
  • [Zha3] -, On even cycle decompositions of eulerian graphs, preprint.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C38, 05C70

Retrieve articles in all journals with MSC: 05C38, 05C70


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1994-1181180-1
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society