Faithful covers, removable circuits and Hamilton weights
by
C.-Q. Zhang
West Virginia University

Let G be a bridgeless cubic graph associated with an eulerian weight w: E(G) → { 1, 2 }. A family F of circuits (cycles) is a faithful circuit (cycle) 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 does not has a 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 an essentially 4-edge-connected, minimal contra pair, then the graph G must be a permutation graph with all weight 2 edges inducing a perfect matching between two chordless circuits. 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: February 20, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cauz-05.