Graphs with the circuit cover property
Brian Alspach, Luis Goddyn, Cun Quan Zhang · Transactions of the American Mathematical Society · 1994
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 ) 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.