Cycle double covers and the semi-Kotzig frame

DOI10.1016/J.EJC.2011.12.001MaRDI QIDQ412256zbMATH OpenOpenAlexFDO

Authors Cun-Quan Zhang, Dong Ye

Publication date 4 May 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.5190

zbMATH Keywords

semi-Kotzig frame

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Let $H$ be a cubic graph admitting a 3-edge-coloring $c:E(H)omathbb{Z}_3$ such that the edges colored by 0 and $muin1,2$ induce a Hamilton circuit of $H$ and the edges colored by 1 and 2 induce a 2-factor $F$. The graph $H$ is semi-Kotzig if switching colors of edges in any even subgraph of $F$ yields a new 3-edge-coloring of $H$ having the same property as $c$. A spanning subgraph $H$ of a cubic graph $G$ is called a {em semi-Kotzig frame} if the contracted graph $G/H$ is even and every non-circuit component of $H$ is a subdivision of a semi-Kotzig graph. In this paper, we show that a cubic graph $G$ has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn (1988), and H"{a}ggkvist and Markstr"{o}m [J. Combin. Theory Ser. B (2006)].

Recommendations

• Cycle double covers and non-separating cycles
• Kotzig frames and circuit double covers
• Signed cycle double covers
• Cycles of covers
• Cycle double covers via kotzig graphs
• scientific article; zbMATH DE number 1790882
• STACS 2005
• Covering odd cycles
• scientific article; zbMATH DE number 5809

Cites work

• scientific article; zbMATH DE number 446493 (Why is no real title available?)
• scientific article; zbMATH DE number 3937197 (Why is no real title available?)
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• scientific article; zbMATH DE number 3600081 (Why is no real title available?)
• scientific article; zbMATH DE number 3276424 (Why is no real title available?)
• Cycle double covers and spanning minors. I
• Cycle double covers and spanning minors. II
• Cycle double covers of graphs with Hamilton paths
• Double covers of cubic graphs with oddness 4
• Edge-Disjoint Spanning Trees of Finite Graphs
• Five cycle double covers of some cubic graphs
• Graphs with the Circuit Cover Property
• Kotzig frames and circuit double covers
• Maximum matching and a polyhedron with 0,1-vertices
• On cycle-double covers of graphs of small oddness
• On the Problem of Decomposing a Graph into n Connected Factors
• On the asymptotics of nodes of \(L^ 2\)-solutions of Schrödinger equations in dimensions \(\geq 3\)
• Polyhedral decompositions of cubic graphs
• Semi-duality and the cycle double cover conjecture

Cited in

(8)

• On semiextensions and circuit double covers
• A note on semiextensions of stable circuits
• Circuit double covers of graphs
• Kotzig frames and circuit double covers
• Cycle double covers via kotzig graphs
• Cycle double covers and spanning minors. I
• Multicover Ucycles
• Circuit extension and circuit double cover of graphs

This page was built for publication: Cycle double covers and the semi-Kotzig frame

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412256)