connected dominating set; connected domatic number; planar
A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The connected domatic number of $G$ is the maximum number of pairwise disjoint, connected dominating sets in $V(G)$. We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.
[CL86] G. Chartrand and L. Lesniak: Graphs and Digraphs
. Prindle, Weber & Schmidt, Boston, 1986. MR 0834583
[H96] S. T. Hedetniemi: personal communication.
[HHR97] S. M. Hedetniemi, S. T. Hedetniemi and R. Reynolds: Combinatorial Problems on Chessboards: II, Chapter 6. Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1997.
[HL84] S. T. Hedetniemi and R. Laskar: Connected domination in graphs
. Graph Theory and Combinatorics, Academic Press, London-New York, 1984, pp. 209–217. MR 0777177
[SW79] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph
. J. Math. Phys. Sci. 13 (1979), 607–613. MR 0575817