Geodesic
An upper bound for domination number of 5-regular graphs
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 1049-1061 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $G=(V, E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.
Let $G=(V, E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.
Classification : 05C69
Keywords: domination number; 5-regular graph; upper bounds 
@article{CMJ_2006_56_3_a22,
     author = {Xing, Hua-Ming and Sun, Liang and Chen, Xue-Gang},
     title = {An upper bound for domination number of 5-regular graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1049--1061},
     year = {2006},
     volume = {56},
     number = {3},
     mrnumber = {2261676},
     zbl = {1164.05425},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a22/}
}
TY  - JOUR
AU  - Xing, Hua-Ming
AU  - Sun, Liang
AU  - Chen, Xue-Gang
TI  - An upper bound for domination number of 5-regular graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 1049
EP  - 1061
VL  - 56
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a22/
LA  - en
ID  - CMJ_2006_56_3_a22
ER  - 
%0 Journal Article
%A Xing, Hua-Ming
%A Sun, Liang
%A Chen, Xue-Gang
%T An upper bound for domination number of 5-regular graphs
%J Czechoslovak Mathematical Journal
%D 2006
%P 1049-1061
%V 56
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a22/
%G en
%F CMJ_2006_56_3_a22
Xing, Hua-Ming; Sun, Liang; Chen, Xue-Gang. An upper bound for domination number of 5-regular graphs. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 1049-1061. http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a22/

[1] Y.  Caro, Y.  Roditty: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20 (1985), 167–180. | MR

[2] Y.  Caro, Y.  Roditty: A note on the $k$-domination number of a graph. Internat.  J. Math. Sci. 13 (1990), 205–206. | DOI | MR

[3] T. W.  Haynes, S. T.  Hedetniemi, and P. J.  Slater: Fundamentals of domination in graphs. Marcel Dekker, New York, 1998. | MR

[4] H.  Liu, L.  Sun: On domination number of 4-regular graphs. Czechoslovak Math.  J. 54 (2004), 889–898. | DOI | MR

[5] W.  McGuaig, B.  Shepherd: Domination in graphs with minimum degree two. J.  Graph Theory 13 (1989), 749–762. | DOI | MR

[6] O.  Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. Vol.  38. Amer. Math. Soc., Providence, 1962. | MR

[7] B.  Reed: Paths, stars, and the number three. Comb. Prob. Comp. 5 (1996), 277–295. | DOI | MR | Zbl

[8] H.  Xing: The upper bounds on domination number of 6-regular graphs. Manuscript.