Small cycle double covers of 4-connected planar graphs (Q1316653)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Small cycle double covers of 4-connected planar graphs |
scientific article |
Statements
Small cycle double covers of 4-connected planar graphs (English)
0 references
18 April 1994
0 references
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.
0 references
cyclic double cover
0 references
planar graph
0 references
Hamilton cycle
0 references
cycle decomposition
0 references
even graph
0 references
0 references