Cycle covers, minimal contra pairs and Hamilton weights
by
CQ Zhang
WVU

Let G be a bridgeless cubic graph associated with an eulerian weight w: E(G) → { 1, 2 }. A family F of circuits is a faithful circuit cover of the ordered pair (G, w) if every edge e of G is contained in precisely w(e) members of F. A circuit C of G is removable if the graph obtained from G by deleting all weight 1 edges contained in C remains bridgeless. An ordered pair (G, w) is a contra pair if it has no faithful circuit cover, and a contra pair is minimal if (G, w) has no removable circuit and, for every weight 2 edge e, the ordered pair (G-e, w) has a faithful circuit cover. It is proved by Alspach, Goddyn and Zhang (Tran. AMS 1994) that if (G, w) is minimal contra pair, then the graph G must be a permutation graph. By applying a theorem of Ellingham (1984), this graph must contain a Petersen minor. It is further conjectured by Fleischner and Jackson (1988) that this graph G must be the Petersen graph itself (not as a minor). In this paper, we prove that this conjecture is implied by the conjecture of Hamilton weight.

Date received: March 3, 2008