The number of independent sets in a connected graph and its complement

Abstract

For a connected graph G, the total number of independent vertex sets (including the empty vertex set) is denoted by i(G). In this paper, we consider Nordhaus-Gaddum-type inequalities for the number of independent sets of a connected graph with connected complement. First we define a transformation on a graph that increases i(G) and i(G). Next, we obtain the minimum and maximum value of i(G) + i(G), where graph G is a tree T with connected complement and a unicyclic graph G with connected complement, respectively. In each case, we characterize the extremal graphs. Finally, we establish an upper bound on the i(G) in terms of the Wiener polarity index.