Displaying similar documents to “ N 2 -locally connected graphs and their upper embeddability”

Connected domatic number in planar graphs

Bert L. Hartnell, Douglas F. Rall (2001)

Czechoslovak Mathematical Journal

Similarity:

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