| Title:
|
Connected domatic number in planar graphs (English) |
| Author:
|
Hartnell, Bert L. |
| Author:
|
Rall, Douglas F. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
51 |
| Issue:
|
1 |
| Year:
|
2001 |
| Pages:
|
173-179 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
connected dominating set |
| Keyword:
|
connected domatic number |
| Keyword:
|
planar |
| MSC:
|
05C10 |
| MSC:
|
05C40 |
| MSC:
|
05C69 |
| MSC:
|
05C70 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1079.05512 |
| idMR:
|
MR1814642 |
| . |
| Date available:
|
2009-09-24T10:41:04Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127636 |
| . |
| Reference:
|
[CL86] G. Chartrand and L. Lesniak: Graphs and Digraphs.Prindle, Weber & Schmidt, Boston, 1986. MR 0834583 |
| Reference:
|
[H96] S. T. Hedetniemi: personal communication.. |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[SW79] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph.J. Math. Phys. Sci. 13 (1979), 607–613. MR 0575817 |
| Reference:
|
[Z86] B. Zelinka: Connected domatic number of a graph.Math. Slovaca 36 (1986), 387–392. Zbl 0625.05042, MR 0871778 |
| . |
