A Characterisation of Graphs with Minimum Degree \(2\) and Domination Number Exceeding a Third their Size

Michael A.Henning1
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.