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/

[1] M. Blank, “An estimate of the external stability of a graph without pendant vertices”, Prikl. Math. i Programmirovanie, 10 (1973), 3–11 | MR

[2] M. Cropper, D. Greenwell, A. J. W. Hilton, and A. V. Kostochka, “The domination number of cubic hamiltonian graphs”, AKCE J. Graphs Combin., 2 (2005), 137–144 | MR | Zbl

[3] K. Kawarabayashi, M. Plummer, and A. Saito, “Domination in a graph with a $2$-factor”, J. of Graph Theory, 52 (2006), 1–6 | DOI | MR | Zbl

[4] A. K. Kelmans, Counterexamples to the Cubic Graph Domination Conjecture, submitted

[5] A. V. Kostochka and B. Y. Stodolsky, “On domination in connected cubic graphs”, Discrete Math., 304 (2005), 45–50 | DOI | MR | Zbl

[6] A. V. Kostochka and B. Y. Stodolsky, “An upper bound on domination number of $n$-vertex connected cubic graphs”, Discrete Math. (to appear) | MR

[7] C. Löwenstein and D. Rautenbach, “Domination in graphs of minimum degree at least two and large girth”, Graphs Combin., 24 (2008), 37–46 | DOI | MR | Zbl

[8] O. Ore, Theory of Graphs, Amer. Math. Soc. Coll. Publ., 38, 1962 | Zbl

[9] M. Plummer, personal communication

[10] B. Reed, “Paths, stars, and the number three”, Combin. Probab. Comput., 5 (1996), 277–295 | DOI | MR | Zbl

[11] B. Y. Stodolsky, On domination in $2$-connected cubic graphs, submitted