Transactions on Combinatorics (Sep 2017)
Common extremal graphs for three inequalities involving domination parameters
Abstract
Let $delta (G)$, $Delta (G)$ and $gamma(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) leq delta(G) + 1$, $d(G)gamma(G) leq |V(G)|$ cite{ch}, and $|V(G)| leq (Delta(G)+1)gamma(G)$ cite{berge}. In this paper, we investigate the graphs $G$ for which all the above inequalities become simultaneously equalities.
Keywords
