Small cycle double covers of 4-connected planar graphs
type: Item
instance of: scholarly article
title: Small cycle double covers of 4-connected planar graphs
zbMATH Open document ID: 0794.05058
DOI: 10.1007/BF01303519
author: K. Seyffarth
published in: Combinatorica
publication date: 1994-04-18T00:00:00Z
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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 522718
zbMATH Keywords: cyclic double cover
zbMATH Keywords: planar graph
zbMATH Keywords: Hamilton cycle
zbMATH Keywords: cycle decomposition
zbMATH Keywords: even graph
MaRDI profile type: Publication
cites work: Q3360905
cites work: What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
cites work: Q3718751
cites work: Flows and generalized coloring theorems in graphs
cites work: Maximal planar graphs of diameter two
cites work: Hajós' conjecture and small cycle double covers of planar graphs
cites work: Polyhedral decompositions of cubic graphs
cites work: A Theorem on Planar Graphs
description: scientific article; zbMATH DE number 522718