DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Cycles intersecting edge-cuts of prescribed sizes

Tomáš Kaiser, Riste Škrekovski

Abstract


We prove that every cubic bridgeless graph G contains a 2-factor which intersects all (minimal) edge-cuts of size 3 or 4. This generalizes an earlier result of the authors, namely that such a 2-factor exists provided that G is planar. As a further extension, we show that every graph contains a cycle (a union of edge-disjoint circuits) that intersects all edge-cuts of size 3 or 4. Motivated by this result, we introduce the concept of a coverable set of integers and discuss a number of questions, some of which are related to classical problems of graph theory such as Tutte's 4-flow conjecture or the Dominating circuit conjecture.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional