Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
MathSciNet review: 1181180
Full-text PDF Free Access

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?)


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: http://dx.doi.org/10.1090/S0002-9947-1994-1181180-1
PII: S 0002-9947(1994)1181180-1
Article copyright: © Copyright 1994 American Mathematical Society