Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
regular graph; dominating set; domination number
regular graph; dominating set; domination number
Summary:
Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$, if for any vertex $v \in V~- S$ there exists a vertex $u \in S$ such that $uv \in E (G)$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma (G) \le \frac{4}{11}n$.
References:
[1] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, 1998. MR 1605684
[2] W. McGuaig and B. Shepherd: Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749–762. MR 1025896
[3] O. Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. (AMS, Providence, RI) 38 (1962). MR 0150753 | Zbl 0105.35401
[4] B. Reed: Paths, stars, and the number three. Comb. Prob. Comp. 5 (1996), 277–295. DOI 10.1017/S0963548300002042 | MR 1411088 | Zbl 0857.05052
Search
Partner of
