Geodesic
A~new bound on the domination number of connected cubic graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 6 (2009), pp. 465-504

Voir la notice de l'article provenant de la source Math-Net.Ru

In 1996, Reed proved that the domination number, $\gamma(G)$, of every $n$-vertex graph $G$ with minimum degree at least $3$ is at most $3n/8$. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper, improving an upper bound by Kostochka and Stodolsky we show that for $n>8$ the domination number of every $n$-vertex cubic connected graph is at most $\lfloor 5n/14\rfloor$. This bound is sharp for even $8$.
Keywords: cubic graphs, connected graphs.
Mots-clés : domination 
@article{SEMR_2009_6_a22,
     author = {A. V. Kostochka and C. Stocker},
     title = {A~new bound on the domination number of connected cubic graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {465--504},
     publisher = {mathdoc},
     volume = {6},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2009_6_a22/}
}
TY  - JOUR
AU  - A. V. Kostochka
AU  - C. Stocker
TI  - A~new bound on the domination number of connected cubic graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2009
SP  - 465
EP  - 504
VL  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2009_6_a22/
LA  - en
ID  - SEMR_2009_6_a22
ER  - 
%0 Journal Article
%A A. V. Kostochka
%A C. Stocker
%T A~new bound on the domination number of connected cubic graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2009
%P 465-504
%V 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2009_6_a22/
%G en
%F SEMR_2009_6_a22
A. V. Kostochka; C. Stocker. A~new bound on the domination number of connected cubic graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 6 (2009), pp. 465-504. http://geodesic.mathdoc.fr/item/SEMR_2009_6_a22/