Connected Domatic Number in Planar Graphs |
| |
Authors: | Bert L Hartnell Douglas F Rall |
| |
Institution: | (1) Saint Mary's University, Halifax, Nova Scotia, Canada, B3H 3C3;(2) Furman University, Greenville, SC, 29613, U.S.A |
| |
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. |
| |
Keywords: | connected dominating set connected domatic number planar |
本文献已被 SpringerLink 等数据库收录! |
|