Some new results on the b-domatic number of graphs

Mohamed Benattalah, Mustapha Chellali, Noureddine Ikhlef-Eschouf


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.


domatic number, b-domatic number, Nordhaus-Gaddum inequalities

Full Text:




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.


  • There are currently no refbacks.

ISSN: 2338-2287

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

View EJGTA Stats