Some new results on the b-domatic number of graphs

Electronic Journal of Graph Theory and Applications

Noureddine Ikhlef-Eschouf¹  Mustapha Chellali²  Mohamed Benattalah³ 

[1] Department of Mathematics and Computer Science, Faculty of Sciences, University Dr. Yahia Farès of Médéa, Algeria.;LAMDA-RO Laboratory, Department of MathematicsUniversity of Blida, Algeria.;RECITS Laboratory, Faculty of SciencesUZA, Djelfa, Algeria.;

关键词: domatic number, b-domatic number, nordhaus-gaddum inequalities;   

DOI  :  10.5614/ejgta.2021.9.1.5

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown