Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
domination number; 5-regular graph; upper bounds
domination number; 5-regular graph; upper bounds
Summary:
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$.
References:
[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.
Search
Partner of
