Change search
ReferencesLink to record
Permanent link

Direct link
Cycle double covers in cubic graphs having special structures
Vienna Univ Technol, Dept Data Bases & Artificial Intelligence, Inst Informat Syst, A-1040 Vienna, Austria.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2014 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 77, no 2, 158-170 p.Article in journal (Refereed) Published
Abstract [en]

In the first part of this article, we employ Thomason's Lollipop Lemma [25] 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 2k-circuit C together with an induced 4k-circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.

Place, publisher, year, edition, pages
2014. Vol. 77, no 2, 158-170 p.
Keyword [en]
CDC, Lollipop
National Category
URN: urn:nbn:se:umu:diva-94547DOI: 10.1002/jgt.21779ISI: 000341710300005OAI: diva2:761454
Available from: 2014-11-06 Created: 2014-10-13 Last updated: 2014-11-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Häggkvist, Roland
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Graph Theory

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link