Some new results on the b-domatic number of graphs
| Main Authors: | Benattalah, Mohamed; RECITS Laboratory, Faculty of Sciences UZA, Djelfa, Algeria., Chellali, Mustapha; LAMDA-RO Laboratory, Department of Mathematics University of Blida, Algeria., Ikhlef-Eschouf, Noureddine; Department of Mathematics and Computer Science, Faculty of Sciences, University Dr. Yahia Farès of Médéa, Algeria. |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/591 https://www.ejgta.org/index.php/ejgta/article/view/591/pdf_160 |
Daftar Isi:
- 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.