Premium
Cycle Double Covers in Cubic Graphs having Special Structures
Author(s) -
Fleischner Herbert,
Häggkvist Roland
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21779
Subject(s) - lemma (botany) , cubic graph , combinatorics , mathematics , graph , discrete mathematics , cover (algebra) , line graph , voltage graph , mechanical engineering , ecology , poaceae , engineering , biology
In the first part of this article, we employ Thomason's Lollipop Lemma [25][A. Thomason, 1978] to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2‐factor F having two components admit CDCs containing any of the components in the 2‐factor, although it need not have a CDC containing all of F . As another example consider a cubic bridgeless graph containing a 2‐factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2 k ‐circuit C together with an induced 4 k ‐circuit T and an independent set of 2 k vertices, each joined by one edge to C and two edges to T , has a CDC starting with T .