Graphs with Constant Sum of Domination and Inverse Domination Numbers

Abstract EN

A subset D of the vertex set of a graph G, is a dominating set if every vertex in V−D is adjacent to at least one vertex in D.

The domination number γ(G) is the minimum cardinality of a dominating set of G.

A subset of V−D, which is also a dominating set of G is called an inverse dominating set of G with respect to D.

The inverse domination number γ′(G) is the minimum cardinality of the inverse dominating sets.

Domke et al.

(2004) characterized connected graphs G with γ(G)+γ′(G)=n, where n is the number of vertices in G.

It is the purpose of this paper to give a complete characterization of graphs G with minimum degree at least two and γ(G)+γ′(G)=n−1.