Domination in graphs of minimum degree five. (English) Zbl 1091.05054

Xing, Huaming; Sun, Liang; Chen, Xuegang

Graphs Comb. 22, No. 1, 127-143 (2006).

Summary: Let \(G = (V,E)\) be a simple graph. A subset \(D\) of \(V\) is a dominating set of \(G\), if for any vertex \(x \in V-D\), there exists a vertex \(y \in D\) such that \(xy \in E\). By using the so-called vertex disjoint paths cover introduced by B. Reed [Comb. Probab. Comput. 5, 277–295 (1996; Zbl 0857.05052)], in this paper we prove that every graph \(G\) on \(n\) vertices with minimum degree at least five has a dominating set of order at most \(5n/14\).

MSC:

05C69

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

Domination number; Vertex disjoint paths cover; Upper bounds

Citations:

Zbl 0857.05052

References:

[1]	Caro, Y., Roditty, Y.: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20, 167–180 (1985) · Zbl 0623.05031
[2]	Caro, Y., Roditty, Y.: A note on the k-domination number of a graph. Internat. J. Math. Sci. 13, 205-206 (1990) · Zbl 0706.05033
[3]	Clark, W. E., Dunning, L. A.: Tight upper bounds for the domination numbers of graphs with given order and minimum degree. Electronic Journal of Combinatorics. 4 (1997),#R26 · Zbl 0884.05057
[4]	Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of domination in graphs. Marcel Dekker, 1998 · Zbl 0890.05002
[5]	McGuaig, W., Shepherd, B.: Domination in graphs with minimum degree two. J. Graph Theory 13, 749-762 (1989) · Zbl 0708.05058
[6]	Ore, O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38(Amer. Math. Soc. Providence, RI) 1962 · Zbl 0105.35401
[7]	Reed, B.: Paths, stars, and the number three. Comb. Prob. Comp. 5, 277-295 (1996) · Zbl 0857.05052
[8]	Sohn, M. Y., Yuan, X.: Domination in graphs of minimum degree four. Manuscript · Zbl 1226.05200