Universal and Global Irredundancy in Graphs

Abstract

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.