Geodesic
Cycles intersecting edge-cuts of prescribed sizes
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a74,
     author = {Kaiser, Tom\'a\v{s} and \v{S}krekovski, Riste},
     title = {Cycles intersecting edge-cuts of prescribed sizes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3465},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3465/}
}
TY  - JOUR
AU  - Kaiser, Tomáš
AU  - Škrekovski, Riste
TI  - Cycles intersecting edge-cuts of prescribed sizes
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3465/
DO  - 10.46298/dmtcs.3465
LA  - en
ID  - DMTCS_2005_special_250_a74
ER  - 
%0 Journal Article
%A Kaiser, Tomáš
%A Škrekovski, Riste
%T Cycles intersecting edge-cuts of prescribed sizes
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3465/
%R 10.46298/dmtcs.3465
%G en
%F DMTCS_2005_special_250_a74
Kaiser, Tomáš; Škrekovski, Riste. Cycles intersecting edge-cuts of prescribed sizes. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3465. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3465/

Cité par Sources :