Nordhaus-Gaddum bounds for domination sums of graphs with minimum degree at least two or three

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 γ(G) of a graph G is the minimum cardinality of a dominating set in G. The complement of a graph G is denoted by Ḡ. In 2005, Dunbar, Haynes and Hedetniemi presented sharp upper bounds for γ(G) + γ(Ḡ) for graphs which have minimum degree at least two or three. In this paper we investigate the graphs achieving these bounds, and we present a new proof in the case that the minimum degree is at least three.