Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
connected dominating set; connected domatic number; planar
connected dominating set; connected domatic number; planar
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.
References:
[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
[Z86] B. Zelinka: Connected domatic number of a graph. Math. Slovaca 36 (1986), 387–392. MR 0871778 | Zbl 0625.05042
Search
Partner of
