Reed, Bruce Paths, stars and the number three. (English) Zbl 0857.05052 Comb. Probab. Comput. 5, No. 3, 277-295 (1996). A dominating set for a graph \(G\) is a set \(D\) of vertices of \(G\) such that every vertex in \(V(G)-D\) has a neighbour in \(D\). In this paper it is proved that any graph \(G\) of order \(n\) with minimum degree at least 3 has a dominating set of size at most \(3n/8\). This is the same as saying that the graph can be covered by at most \(3n/8\) stars (a star \(S\) being a vertex \(v\) with edges to all vertices in \(S-v\)). It is also shown that any connected cubic graph \(G\) of order \(n\) can be covered by \(\lceil n/9\rceil\) vertex disjoint paths. Both of these results are sharp. Reviewer: C.Jagger (Cambridge) Cited in 15 ReviewsCited in 67 Documents MSC: 05C35 Extremal problems in graph theory 05C38 Paths and cycles Keywords:dominating set; star; cubic graph; paths PDF BibTeX XML Cite \textit{B. Reed}, Comb. Probab. Comput. 5, No. 3, 277--295 (1996; Zbl 0857.05052) Full Text: DOI OpenURL References: [1] Payan, Cahiers C.E.R.O. 17 pp 307– (1975) [2] DOI: 10.1002/jgt.3190130610 · Zbl 0708.05058 [3] DOI: 10.1016/0012-365X(75)90058-8 · Zbl 0323.05127 [4] Arnautov, Prikl. Mat. i Programmirovanie Vyp. 11 pp 3– (1974) [5] DOI: 10.1002/net.3230070305 · Zbl 0384.05051 [6] Blank, Prikl. Math, i Programmirovanie Vyp. 10 pp 3– (1973) [7] Edmonds, Can. J. Math. 17 pp 449– (1964) · Zbl 0132.20903 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.