Small cycle double covers of 4-connected planar graphs

DOI10.1007/BF01303519MaRDI QIDQ1316653zbMATH OpenFDO

Authors K. Seyffarth

Publication date 18 April 1994

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01303519

zbMATH Keywords

cycle decompositioncyclic double covereven graphHamilton cycleplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A cyclic double cover of a graph, \(G\), is a collection of cycles, \(\mathcal C\), such that every edge of \(G\) lies in precisely two cycles of \(\mathcal C\). The Small Cycle Double Cover (SCDC) Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph on \(n\) vertices has a cycle double cover with at most \(n-1\) cycles, and is a strengthening of the well-known Cycle Double Cover Conjecture. This paper contains a proof of the SCDC Conjecture for 4-connected planar graphs. The proof relies on two main results. The first, due to W. T. Tutte, states that every 4- connected planar graph contains a Hamilton cycle. The second result concerns the minimum number of cycles in the cycle decomposition of an even planar graph. An even graph is one in which all vertices have even degree, and a cycle decomposition of an even graph is a partition of the edge set of the graph into cycles. Let \(c(G)\) denote the minimum number of cycles required in a cycle decomposition of an even graph \(G\). There exist even graphs \(G\) on \(n\) vertices for which \(c(G)\geq \lfloor (n-1)/2\rfloor\), and G. Hajós conjectured that every simple even graph \(G\) on \(n\) vertices has \(c(G)\leq \lfloor(n-1)/2\rfloor\). J. Tao and, independently, the author, proved this conjecture for planar graphs, and this fact is used in the proof of the SCDC Conjecture for 4-connected planar graphs. The basic idea behind the proof is the following: let \(G\) be a simple 4- connected planar graph, and \(H\) a Hamilton cycle in \(G\). The cycle \(H\) is used to construct three even subgraphs of \(G\) so that every edge of \(G\) lies in precisely two of the even subgraphs. These even subgraphs are then decomposed into cycles.

Recommendations

• Hajós' conjecture and small cycle double covers of planar graphs
• scientific article; zbMATH DE number 4214053
• scientific article; zbMATH DE number 140148
• Cycle covers of planar 2-edge-connected graphs
• Small oriented cycle double cover of graphs

Cites work

• A Theorem on Planar Graphs
• Flows and generalized coloring theorems in graphs
• Hajós' conjecture and small cycle double covers of planar graphs
• scientific article; zbMATH DE number 4214053 (Why is no real title available?)
• scientific article; zbMATH DE number 3948320 (Why is no real title available?)
• Maximal planar graphs of diameter two
• Polyhedral decompositions of cubic graphs
• What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?

Cited in

(10)

• Small cycle double covers of products. II: Categorical and strong products with paths and cycles
• Hajós' conjecture and small cycle double covers of planar graphs
• Classes of line graphs with small cycle double covers
• scientific article; zbMATH DE number 4177081 (Why is no real title available?)
• scientific article; zbMATH DE number 3885954 (Why is no real title available?)
• scientific article; zbMATH DE number 4214053 (Why is no real title available?)
• scientific article; zbMATH DE number 1185135 (Why is no real title available?)
• Circuit double covers of graphs
• Small oriented cycle double cover of graphs
• The edge labeling of higher order Voronoi diagrams

This page was built for publication: Small cycle double covers of 4-connected planar graphs

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