### Some new results on the b-domatic number of graphs

#### Abstract

A domatic partition *P* of a graph *G*=(*V*,*E*) is a partition of *V* into classes that are pairwise disjoint dominating sets. Such a partition *P* is called *b*-maximal if no larger domatic partition *P' *can be obtained by gathering subsets of some classes of *P* to form a new class. The *b*-domatic number *bd*(*G*) is the minimum cardinality of a *b*-maximal domatic partition of *G*. In this paper, we characterize the graphs *G* of order *n* with *bd*(*G*) ∈ {*n*-1,*n*-2,*n*-3}. Then we prove that for any graph *G* on *n* vertices, *bd*(*G*)+*bd*(*Ġ*) ≤ *n*+1, where *Ġ* is the complement of *G*. Moreover, we provide a characterization of the graphs *G* of order *n* with *bd*(*G*)+*bd*(*Ġ*) ∈ {*n*+1,*n*} as well as those graphs for which *bd*(*G*)=*bd*(*Ġ*)=*n*/2.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.5

#### References

J. Amjadi, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Total Roman domatic number of a graph, Asian-Eur. J. Math. 13 (2020) Article ID: 2050110.

G.J. Chang, The domatic number problem, Discrete Math. 125 (1994), 115–122.

E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247–261.

O. Favaron, The b-domatic number of a graph. Discuss. Math. Graph Theory 33 (2013), 747–757.

M. Benatallah, N. Ikhlef Eschouf, and M. Mihoubi, On the b-domatic number of graphs. Discuss. Math. Graph Theory 39 (2019), 313–324.

J.E. Dunbar, T.W. Haynes, and M.A. Henning, Nordhaus-Gaddum type results for the domatic number of a graph. In Combinatorics, Graph Theory, and Algorithms, vols. I, II, New Issues Press, Kalamazoo (1999), 303–312.

F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969.

S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a digraph, Electron. J. Graph Theory Appl. 3 (1) (2015), 85–93.

L. Volkmann, The Roman {2}-domatic number of graphs. Discrete Appl. Math. 258 (2019), 235–241.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.