Cycles intersecting edge-cuts of prescribed sizes
Kaiser, Tomáš ; Škrekovski, Riste
HAL, hal-01184454 / Harvested from HAL
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.
Publié le : 2005-07-04
Classification:  graph,  cycle,  edge-cut,  covering cycle,  coverable set,  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-01184454,
     author = {Kaiser, Tom\'a\v s and \v Skrekovski, Riste},
     title = {Cycles intersecting edge-cuts of prescribed sizes},
     journal = {HAL},
     volume = {2005},
     number = {0},
     year = {2005},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01184454}
}
Kaiser, Tomáš; Škrekovski, Riste. Cycles intersecting edge-cuts of prescribed sizes. HAL, Tome 2005 (2005) no. 0, . http://gdmltest.u-ga.fr/item/hal-01184454/