umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Cycle double covers and spanning minors I
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2006 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 96, no 2, 183-206 p.Article in journal (Refereed) Published
Abstract [en]

Define a graph to be a Kotzig graph if it is $m$-regular and has an $m$-edge colouring in which each pair of colours form a Hamiltonian cycle. We show that every cubic graph with spanning subgraph consisting of a subdivision of a Kotzig graph together with even cycles has a cycle double cover, in fact a 6-CDC. We prove this for two other families of graphs similar to Kotzig graphs as well. In particular, let $F$ be a 2-factor in a cubic graph $G$ and denote by $G_{F}$ the pseudograph obtained by contracting each component in $F$. We show that if there exist a cycle in $G_{F}$ through all vertices of odd degree, then $G$ has a CDC. We conjecture that every 3-connected cubic graph contains a spanning subgraph homeomorphic to a Kotzig graph. In a sequel we show that every cubic graph with a spanning homeomorph of a 2-connected cubic graph on at most 10 vertices has a CDC.

Place, publisher, year, edition, pages
New York etc.: Academic Press , 2006. Vol. 96, no 2, 183-206 p.
Keyword [en]
Cycle double cover, Kotzig; Frame, Cubic graphs
Identifiers
URN: urn:nbn:se:umu:diva-7660DOI: 10.1016/j.jctb.2005.07.004OAI: oai:DiVA.org:umu-7660DiVA: diva2:147331
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2011-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Häggkvist, RolandMarkström, Klas

Search in DiVA

By author/editor
Häggkvist, RolandMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of combinatorial theory. Series B (Print)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 151 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf