Previous |  Up |  Next


domination number; 5-regular graph; upper bounds
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$.
[1] Y.  Caro, Y.  Roditty: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20 (1985), 167–180. MR 0824858
[2] Y.  Caro, Y.  Roditty: A note on the $k$-domination number of a graph. Internat.  J. Math. Sci. 13 (1990), 205–206. DOI 10.1155/S016117129000031X | MR 1038667
[3] T. W.  Haynes, S. T.  Hedetniemi, and P. J.  Slater: Fundamentals of domination in graphs. Marcel Dekker, New York, 1998. MR 1605684
[4] H.  Liu, L.  Sun: On domination number of 4-regular graphs. Czechoslovak Math.  J. 54 (2004), 889–898. DOI 10.1007/s10587-004-6438-0 | MR 2100002
[5] W.  McGuaig, B.  Shepherd: Domination in graphs with minimum degree two. J.  Graph Theory 13 (1989), 749–762. DOI 10.1002/jgt.3190130610 | MR 1025896
[6] O.  Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. Vol.  38. Amer. Math. Soc., Providence, 1962. MR 0150753
[7] B.  Reed: Paths, stars, and the number three. Comb. Prob. Comp. 5 (1996), 277–295. DOI 10.1017/S0963548300002042 | MR 1411088 | Zbl 0857.05052
[8] H.  Xing: The upper bounds on domination number of 6-regular graphs. Manuscript.
Partner of
EuDML logo