Abstract
Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn−1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. A. Bondy: Small cycle double covers of graphs, in:Cycles and Rays (G. Hahn, G. Sabidussi, and R. Woodrow, eds.), NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht, 1990, 21–40.
N. Dean: What is the smallest number of dicycles in a dicycle decomposition of an eulerian graph?,J. Graph Theory 10 (1986), 299–308.
O. Favaron, andM. Kouider: Path partitions and cycle partitions of eulerian graphs of maximum degree 4.Studia Sci. Math. Hungar. 23 (1988), 237–244.
A. Granville, andA. Moisiadis: On Hajós' Conjecture, in:Proceedings of the Sixteenth Manitoba Conference on Numerical Mathematics and Computing, Congressus Numerantium 56 (1987) 183–187.
F. Jaeger: Flows and generalized coloring theorems in graphs,J. Combinatorial Theory, Ser. B 26 (1979), 205–216.
L. Lovász: On covering of graphs, in:Theory of Graphs (P. Erdős and G. O. H. Katona, eds.), Academic Press, 1968, 231–236.
K. Seyffarth:Cycle and Path Covers of Graphs, Ph. D. Thesis, University of Waterloo, 1989.
K. Seyffarth: Hajós' Conjecture and small cycle double cover of planar graphs,Discrete Math. 101 (1992), 291–306.
P. D. Seymour: Sums of circuits, in:Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.), Academic Press, New York, 1979, 341–355.
G. Szekeres: Polyhedral decomposition of cubic graphs,Bull. Austral. Math. Soc. 8 (1973), 367–387.
J. Tao: On Hajós' conjecture (Chinese),J. China Univ. Sci. Tech. 14 (1984), 585–592.
W. T. Tutte: A theorem on planar graphs,Trans. Amer. Math. Soc. 82 (1956), 99–116.