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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references