Stable and Unstable Graphs with Total Irredundance Number Zero

Abstract

For a graph \(G = (V,E)\), a set \(S \subseteq V\) is \(total\; irredundant\) if for every vertex \(v \in V\), the set \(N[v]- N[S – \{v\}]\) is not empty. The \(total \;irredundance\; number\) \(ir_t(G)\) is the minimum cardinality of a maximal total irredundant set of \(G\). We study the structure of the class of graphs which do not have any total irredundant sets; these are called \(ir_t(0)\)-graphs. Particular attention is given to the subclass of \(ir_t(0)\)-graphs whose total irredundance number either does not change (stable) or always changes (unstable) under arbitrary single edge additions. Also studied are \(ir_t(0)\)-graphs which are either stable or unstable under arbitrary single edge deletions.