Geodesic
Connected domatic number in planar graphs
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 1, pp. 173-179
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C10, 05C40, 05C69, 05C70, 05C99
Keywords: connected dominating set; connected domatic number; planar 
@article{CMJ_2001_51_1_a15,
     author = {Hartnell, Bert L. and Rall, Douglas F.},
     title = {Connected domatic number in planar graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {173--179},
     year = {2001},
     volume = {51},
     number = {1},
     mrnumber = {1814642},
     zbl = {1079.05512},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a15/}
}
TY  - JOUR
AU  - Hartnell, Bert L.
AU  - Rall, Douglas F.
TI  - Connected domatic number in planar graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2001
SP  - 173
EP  - 179
VL  - 51
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a15/
LA  - en
ID  - CMJ_2001_51_1_a15
ER  - 
%0 Journal Article
%A Hartnell, Bert L.
%A Rall, Douglas F.
%T Connected domatic number in planar graphs
%J Czechoslovak Mathematical Journal
%D 2001
%P 173-179
%V 51
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a15/
%G en
%F CMJ_2001_51_1_a15
Hartnell, Bert L.; Rall, Douglas F. Connected domatic number in planar graphs. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 1, pp. 173-179. http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a15/

[CL86] G. Chartrand and L. Lesniak: Graphs and Digraphs. Prindle, Weber & Schmidt, Boston, 1986. | MR

[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

[SW79] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph. J. Math. Phys. Sci. 13 (1979), 607–613. | MR

[Z86] B. Zelinka: Connected domatic number of a graph. Math. Slovaca 36 (1986), 387–392. | MR | Zbl