Universal and Global Irredundancy in Graphs

A set \(S\) of vertices of a graph \(G = (V, E)\) is a global dominating set if \(S\) dominates both \(G\) and its complement \(\overline{G}\). The concept of global domination was first introduced by Sampathkumar. In this paper, we extend this notion to irredundancy. A set \(S\) of vertices will be called universal irredundant if \(S\) is irredundant in both \(G\) and \(\overline{G}\). A set \(S\) will be called global irredundant if for every \(x\) in \(S\), \(x\) is an irredundant vertex in \(S\) either in \(G\) or in \(\overline{G}\). We investigate the universal irredundance and global irredundance parameters of a graph. It is also shown that the determination of the upper universal irredundance number of graphs is NP-Complete.