On graphs having equal domination and codomination numbers

Abstract

In a graph G = (V, E), a set S ⊂ V is a dominating set if each vertex of V-S is adjacent to at least one vertex in S. The domination number γ(G) is the smallest order of a dominating set of G and the codomination number of G, written γ(Ḡ), is the domination number of its complement. We investigate conditions under which graphs have equal domination and codomination numbers. In particular, we characterize graphs for which γ(G) = γ(Ḡ) = 2 and establish properties of graphs for which γ(G) = γ(Ḡ) ≥ 3. Finally, we construct a family of graphs having γ(G) = γ(Ḡ).