Geodesic
Avoiding 7-circuits in 2-factors of cubic graphs
Robert Lukoťka1
1Department of Mathematics and Computer Science Faculty of Education Trnava University Trnava
The electronic journal of combinatorics, Tome 21 (2014) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be a cyclically $4$-edge-connected cubic graph with girth at least $7$ on $n$ vertices. We show that $G$ has a $2$-factor $F$ such that at least a linear amount of vertices is not in $7$-circuits of $F$. More precisely, there are at least $n/657$ vertices of $G$ that are not in $7$-circuits of $F$. If $G$ is cyclically $6$-edge-connected then the bound can be improved to $n/189$. As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically $4$-edge-connected ($6$-edge-connected) cubic graph of girth at least $7$.
DOI : 10.37236/4379
Classification : 05C70, 90C27
Mots-clés : cubic graphs, 2-factors

Robert Lukoťka  1

1 Department of Mathematics and Computer Science Faculty of Education Trnava University Trnava 
@article{10_37236_4379,
     author = {Robert Luko\v{t}ka},
     title = {Avoiding 7-circuits in 2-factors of cubic graphs},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {4},
     doi = {10.37236/4379},
     zbl = {1302.05145},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4379/}
}
TY  - JOUR
AU  - Robert Lukoťka
TI  - Avoiding 7-circuits in 2-factors of cubic graphs
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4379/
DO  - 10.37236/4379
ID  - 10_37236_4379
ER  - 
%0 Journal Article
%A Robert Lukoťka
%T Avoiding 7-circuits in 2-factors of cubic graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4379/
%R 10.37236/4379
%F 10_37236_4379
Robert Lukoťka. Avoiding 7-circuits in 2-factors of cubic graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4379

Cité par Sources :