Cycle double covers of graphs with Hamilton paths

DOI10.1016/0095-8956(89)90048-8MaRDI QIDQ1089005zbMATH OpenOpenAlexFDO

Authors Luis Goddyn

Publication date 1989

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(89)90048-8

zbMATH Keywords

cycle double covereulerian subgraphsHamilton path

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A k-cycle double cover of a graph G is a collection Z of at most k eulerian subgraphs of G such that every edge of G is an edge of exactly two subgraphs in Z. Presented is a short proof of the following theorem due to \textit{M. Tarsi} [``Semi-duality and the cycle double cover conjecture, J. Comb. Theory, Ser. B 41, 332-340 (1986; Zbl 0607.05019)]: Every bridgeless graph containing a Hamilton path has a 6- cycle double cover.

Recommendations

• Five cycle double covers of some cubic graphs
• scientific article; zbMATH DE number 5809
• Cycle double covers and long circuits of graphs
• On cycle-double covers of graphs of small oddness
• Cycle covering in bridgeless graphs

Cites work

• scientific article; zbMATH DE number 3937197 (Why is no real title available?)
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• Polyhedral decompositions of cubic graphs
• Relative lengths of paths and cycles in 3-connected graphs
• Semi-duality and the cycle double cover conjecture

Cited in

(17)

• Trigraphs
• Hamilton cycles in double generalized Petersen graphs
• Double covers of cubic graphs with oddness 4
• Five cycle double covers of some cubic graphs
• Nowhere-zero 4-flows and cycle double covers
• Orientable embeddings and orientable cycle double covers of projective-planar graphs
• Some basic properties of multiple Hamiltonian covers
• Cycle covers. II: Circuit chain, Petersen chain and Hamilton weights.
• Double cycle covers and the petersen graph
• Cycle double covers and the semi-Kotzig frame
• Graphs with the Circuit Cover Property
• Double coverings of 2‐paths by Hamilton cycles*
• scientific article; zbMATH DE number 6302979 (Why is no real title available?)
• Circuit double covers of graphs
• The decycling number of a line graph
• Approximate cycle double cover
• Cycle double covers of infinite planar graphs

This page was built for publication: Cycle double covers of graphs with Hamilton paths

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