COMMON EXTREMAL GRAPHS FOR THREE INEQUALITIES INVOLVING DOMINATION PARAMETERS

Let (G), Δ(G) and (G) be the minimum degree, maximum degree and domination number of a graph G = (V (G);E(G)), respectively. A partition of V (G), all of whose classes are dominating sets in G, is called a domatic partition of G. The maximum number of classes of a domatic partition of G is called the domatic number of G, denoted d(G). It is well known that d(G) (G)+1, d(G) (G) jV (G)j [6], and jV (G)j (Δ(G) + 1) (G) [3]. In this paper, we investigate the graphs G for which all the above inequalities become simultaneously equalities.