A characterisation of graphs with minimum degree $2$ and domination number exceeding a third their size

Abstract

Let $G=(V,E)$ be a graph.A set $S\subseteq V$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$.The domination number of $G$, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set of $G$.Sanchis [8] showed that a connected graph $G$ of size $q$ and minimum degree at least $2$ has domination number at most $(q+2)/3$.
In this paper, connected graphs $G$ of size $q$ with minimum degree at least $2$ satisfying $\gamma (G)>\frac{q}{3}$ are characterized.