Cycles intersecting edge-cuts of prescribed sizes

被引:19
作者
Kaiser, Tomas [1 ,2 ]
Skrekovski, Riste [3 ,4 ]
机构
[1] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic
[2] Univ W Bohemia, Inst Theoret Comp Sci, Plzen 30614, Czech Republic
[3] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia
[4] Charles Univ Prague, Inst Theoret Comp Sci, CR-11800 Prague 1, Czech Republic
关键词
graph; edge-cut; coverable set; dominating cycle;
D O I
10.1137/070683635
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 and the Dominating Cycle Conjecture.
引用
收藏
页码:861 / 874
页数:14
相关论文
共 16 条