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

Michael A. Henning 1
1University of Natal Private Bag X01, Scottsville Pietermaritzburg, 3209 South Africa

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.