zbMATH — the first resource for mathematics

On k-ply domatic numbers of graphs. (English) Zbl 0602.05039
A k-ply dominating set in an undirected graph G is a subset D of the vertex set V(G) of G with the property that for each vertex \(x\in V(G)-D\) there exist k pairwise distinct vertices \(y_ 1,...,y_ k\) which are all adjacent to x. The maximum number of classes of a partition of V(G) into k-ply dominating sets is called the k-ply domatic number of G and denoted by \(d^ k(G)\). This is a generalization of the domatic number of a graph which was introduced by E. J. Cockayne and S. T. Hedetniemi. The properties of the k-ply domatic number of a graph are described. Some inequalities are presented and the interrelations among k-ply domatic numbers for different numbers k are treated. The k-ply domatic numbers of circuits and of complete bipartite graphs are stated. At the end edge- critical graphs with respect to the k-ply domatic number are described.

05C35 Extremal problems in graph theory
Full Text: EuDML
[1] COCKAYNE E. J., HEDETNIEMI S. T.: Towards a theory of domination in graphs. Network s7, 1977, 247-261. · Zbl 0384.05051
[2] ZELINKA B.: Domatically critical graphs. Czech. Math. J. 30, 1980, 486-489. · Zbl 0426.05046
[3] ZELINKA B.: On k-domatic numbers of graphs. Czech. Math. J. 33, 1983, 309-313. · Zbl 0537.05050
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.