Connected domatic number in planar graphs. (English) Zbl 1079.05512

Summary: 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.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI EuDML


[1] G. Chartrand and L. Lesniak: Graphs and Digraphs. Prindle, Weber & Schmidt, Boston, 1986.
[2] S. T. Hedetniemi: personal communication.
[3] 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.
[4] S. T. Hedetniemi and R. Laskar: Connected domination in graphs. Graph Theory and Combinatorics, Academic Press, London-New York, 1984, pp. 209-217.
[5] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph. J. Math. Phys. Sci. 13 (1979), 607-613. · Zbl 0449.05057
[6] B. Zelinka: Connected domatic number of a graph. Math. Slovaca 36 (1986), 387-392. · Zbl 0625.05042
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.