On the product of upper irredundance numbers of a graph and its complement (Q1119604)

A closed neighbourhood of a vertex x of a graph G is the set consisting of x and of all vertices which are adjacent to x in G. A vertex x is redundant in a subset X of the vertex set of G, if the closed neighbourhood of x is a subset of the union of closed neighbourhoods of all vertices of \(X=\{x\}\). If X contains no vertex redundant in X, then X is called irredundant. The upper irredundance number \({\mathbb{R}}(G)\) of G is the maximum number of vertices of an irredundant set in G. The paper studies the upper irredundance numbers of a graph G and of its complement \(\bar G.\) The Nordhaus-Gaddum type inequalities \({\mathbb{R}}(G)\). \({\mathbb{R}}(\bar G)\leq \lceil (p^ 2+2p)/4\rceil,\) \({\mathbb{R}}(G)+{\mathbb{R}}(\bar G)\leq p+1,\) where p is the number of vertices of G, are proved.