Article ID Journal Published Year Pages File Type
4656673 Journal of Combinatorial Theory, Series B 2016 28 Pages PDF
Abstract

The Circuit Double Cover Conjecture is one of the most challenging open problems in graph theory. The main result of the paper is related to the characterization of circuit chain structure, which has been one of the most popular approaches to the conjecture. Let G   be a bridgeless cubic graph associated with an eulerian weight w:E(G)→{1,2}w:E(G)→{1,2} such that (G,w)(G,w) does not have a faithful circuit cover. If, for every weight 2 edge e0e0 of (G,w)(G,w), the eulerian weighted graph (G−e0,w)(G−e0,w) has a faithful circuit cover and (G,w)(G,w) has no removable circuit avoiding e0e0, then it was proved (Alspach et al., 1993 [1] or 1994 [2]) that G contains a Petersen minor. It was further conjectured by Fleischner and Jackson (1988) that this graph G must be the Petersen graph. This conjecture was verified (JCTB 2010) recently under the assumption of the Hamilton weight conjecture. These two earlier results are further strengthened in this paper as follows. If, for a given weight 2 edge e0e0, the eulerian weighted graph (G−e0,w)(G−e0,w) has a faithful circuit cover and (G,w)(G,w) has no removable circuit avoiding e0e0, then, under the assumption of the Hamilton weight conjecture, G must be a Petersen chain. With a much weaker requirement “for a given  e0e0” instead of “for every  e0e0”, this strengthened result (structure of circuit chain joining a missing edge) is expected to be much more useful in future studies about circuit covering problems.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,