Connected domatic number in planar graphs

Bert L. Hartnell; Douglas F. Rall

Czechoslovak Mathematical Journal (2001)

  • Volume: 51, Issue: 1, page 173-179
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Hartnell, Bert L., and Rall, Douglas F.. "Connected domatic number in planar graphs." Czechoslovak Mathematical Journal 51.1 (2001): 173-179. <http://eudml.org/doc/30624>.

@article{Hartnell2001,
abstract = {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.},
author = {Hartnell, Bert L., Rall, Douglas F.},
journal = {Czechoslovak Mathematical Journal},
keywords = {connected dominating set; connected domatic number; planar; connected dominating set; connected domatic number; planar},
language = {eng},
number = {1},
pages = {173-179},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Connected domatic number in planar graphs},
url = {http://eudml.org/doc/30624},
volume = {51},
year = {2001},
}

TY - JOUR
AU - Hartnell, Bert L.
AU - Rall, Douglas F.
TI - Connected domatic number in planar graphs
JO - Czechoslovak Mathematical Journal
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 51
IS - 1
SP - 173
EP - 179
AB - 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.
LA - eng
KW - connected dominating set; connected domatic number; planar; connected dominating set; connected domatic number; planar
UR - http://eudml.org/doc/30624
ER -

References

top
  1. Graphs and Digraphs, Prindle, Weber & Schmidt, Boston, 1986. (1986) MR0834583
  2. personal communication, . 
  3. Combinatorial Problems on Chessboards: II, Chapter 6, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1997. (1997) 
  4. Connected domination in graphs, Graph Theory and Combinatorics, Academic Press, London-New York, 1984, pp. 209–217. (1984) MR0777177
  5. The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979), 607–613. (1979) MR0575817
  6. Connected domatic number of a graph, Math. Slovaca 36 (1986), 387–392. (1986) Zbl0625.05042MR0871778

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.