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

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\).


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


Zbl 0857.05052
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.