Paths, stars and the number three. (English) Zbl 0857.05052

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.


05C35 Extremal problems in graph theory
05C38 Paths and cycles
Full Text: DOI


[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.