✦ LIBER ✦

Hajós' conjecture and small cycle double covers of planar graphs

✍ Scribed by Karen Seyffarth

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 865 KB
Volume: 101
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90610-r

No coin nor oath required. For personal study only.

✦ Synopsis

Seyffarth,

K., Hajos' conjecture and small cycle double covers of planar graphs, Discrete Mathematics 101 (1992) 291-306.

We prove that every simple even planar graph on n vertices has a partition of its edge set into at most [(n -1)/2] cycles. A previous proof of this result was given by Tao, but is incomplete, and we provide here a somewhat different proof. We also discuss the connection between this result and the Small Cycle Double Cover Conjecture.

Conjecture 1 (Hajos' Conjecture).

If G is a simple even graph on n vertices, then c(G) < ](n -1)/2].

📜 SIMILAR VOLUMES

Packings and perfect path double covers

Packings and perfect path double covers of maximal planar graphs

✍ Karen Seyffarth 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 817 KB

Seyffarth, K., Packings and perfect path double covers of maximal planar graphs, Discrete Mathematics 117 (1993) 1833195. A maximal planar graph is a simple planar graph in which every face is a triangle, and a perfect packing of such a graph by 2-cliques and facial triangles corresponds to a parti

Small cycle double covers of products I:

Small cycle double covers of products I: Lexicographic product with paths and cycles

✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __