Upper bounds for the domination number in graphs of diameter two

Abstract

A vertex set D of a graph G is a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number 7(G) of a graph G is the minimum cardinality of a dominating set in G. If G is a graph of diameter two and order n ≥ 24, then we prove in this paper that γ(G) ≤ [n/4]. As an application of this bound, we present partial solutions of problems posed by Dunbar, Haynes and Hedetniemi [3] and Volkmann [5].