Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423538 | Discrete Mathematics | 2012 | 7 Pages |
A cubic graph H is called a Kotzig graph if H has a circuit double cover consisting of three Hamilton circuits. It was first proved by Goddyn that if a cubic graph Gcontains a spanning subgraph Hwhich is a subdivision of a Kotzig graph then Ghas a circuit double cover. A spanning subgraph H of a cubic graph G is called a Kotzig frame if the contracted graph G/H is even and every non-circuit component of H is a subdivision of a Kotzig graph. It was conjectured by Häggkvist and Markström (Kotzig Frame Conjecture, JCTB 2006) that if a cubic graph Gcontains a Kotzig frame, then Ghas a circuit double cover. This conjecture was verified for some special cases: it is proved by Goddyn if a Kotzig frame has only one component, by Häggkvist and Markström (JCTB 2006) if a Kotzig frame has at most one non-circuit component. In this paper, the Kotzig Frame Conjecture is further verified for some families of cubic graphs with Kotzig frames H of the following types: (i) a Kotzig frame Hhas at most two components; or (ii) the contracted graph G/His a tree if parallel edges are identified as a single edge. The first result strengthens the theorem by Goddyn. The second result is a further generalization of the first result, and is a partial result to the Kotzig Frame Conjecture for frames with multiple Kotzig components.