On the b-Domatic Number of Graphs

Abstract

A set of vertices S in a graph G = (V, E) is a dominating set if every vertex not in S is adjacent to at least one vertex in S. A domatic partition of graph G is a partition of its vertex-set V into dominating sets. A domatic partition 𝒫 of G is called b-domatic if no larger domatic partition of G can be obtained from 𝒫 by transferring some vertices of some classes of 𝒫 to form a new class. The minimum cardinality of a b-domatic partition of G is called the b-domatic number and is denoted by bd(G). In this paper, we explain some properties of b-domatic partitions, and we determine the b-domatic number of some families of graphs.

Keywords

• domatic partition
• domatic number
• b-domatic partition
• b-domatic number
• 05c15
• 05c69
• 05c70