Some new results on the b-domatic number of graphs

Mohamed Benattalah (RECITS Laboratory, Faculty of Sciences UZA, Djelfa, Algeria.)
Mustapha Chellali (LAMDA-RO Laboratory, Department of Mathematics University of Blida, Algeria.)
Noureddine Ikhlef-Eschouf (Department of Mathematics and Computer Science, Faculty of Sciences, University Dr. Yahia Farès of Médéa, Algeria.)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 1 (2021): Electronic Journal of Graph Theory and Applications

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.