umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Cycle double covers and spanning minors I
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2006 (engelsk)Inngår i: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 96, nr 2, 183-206 s.Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
New York etc.: Academic Press , 2006. Vol. 96, nr 2, 183-206 s.
Emneord [en]
Cycle double cover, Kotzig; Frame, Cubic graphs
Identifikatorer
URN: urn:nbn:se:umu:diva-7660DOI: 10.1016/j.jctb.2005.07.004OAI: oai:DiVA.org:umu-7660DiVA: diva2:147331
Tilgjengelig fra: 2008-01-11 Laget: 2008-01-11 Sist oppdatert: 2017-12-14bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler

Andre lenker

Forlagets fulltekst

Søk i DiVA

Av forfatter/redaktør
Häggkvist, RolandMarkström, Klas
Av organisasjonen
I samme tidsskrift
Journal of combinatorial theory. Series B (Print)

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 165 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf