Connected domination in graphs. (English) Zbl 0548.05055

Graph theory and combinatorics, Proc. Conf. Hon. P. Erdös, Cambridge 1983, 209-217 (1984).
[For the entire collection see Zbl 0543.00003.]
A set D of vertices in a graph G is said to be a connected dominating set in G if every vertex in V(G)-D is adjacent to at least one vertex in D and the subgraph of G induced by D is connected. The connected domination number \(\gamma_ c(G)\) is the minimum number of vertices in a connected dominating set in G. The authors prove a number of results which relate \(\gamma_ c\) to other parameters of a graph, extending thereby results of E. Sampathkumar and H. B. Walikar [J. Math. Phys. Sci. 13, 607-613 (1979; Zbl 0449.05057)], J. Nieminen [J. Inst. Math. Appl. 14, 183-187 (1974; Zbl 0288.05124)], and E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi [Networks 10, 211-219 (1980; Zbl 0447.05039)].
Reviewer: J.Širáň


05C99 Graph theory