Connected domatic number of a graph. (English) Zbl 0625.05042

The connected domatic number of a graph G is the maximum number of subsets in a partition of V(G), each of whose subsets D has the properties that (i) the subgraph induced by it is connected and (ii) for each vertex \(x\in V(G)-D\), there exists a vertex \(y\in D\) adjacent to x. The connected domatic number if well defined only for connected graphs. The author studies a number of properties of the connected domatic number.
Reviewer: G.Chartrand


05C99 Graph theory
Full Text: EuDML


[1] COCKAYNE E. J., HEDETNIEMI S. T.: Towards a theory of domination in graphs. Networks 7, 1977, 247-261. · Zbl 0384.05051
[2] COCKAYNE E. J., DAWES R., HEDETNIEMI S. T.: Total domination in graphs. Networks 10, 1980, 211-219. · Zbl 0447.05039
[3] LASKAR R., HEDETNIEMI S. T.: Connected Domination in Graphs. Tech. Report 414, Clemson Univ., Clemson, South Carolina, March 1983. · Zbl 0548.05055
[4] JAEGAR F., PAYAN C.: Relations du type Nordhaus-Gaddum pour le numbre d’absorption d’un graphe simple. C. R. Acad. Sci. Paris, Series A 274, 1972, 728-730. · Zbl 0226.05121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.