Sensitivity of the Upper Irredundance Number to Edge Addition

Abstract

In this study, we consider the effect on the upper irredundance number $IR(G)$ of a graph $G$ when an edge is added joining a pair of non-adjacent vertices of $G$. We say that $G$ is $IR$-insensitive if $IR(G+e)=IR(G)$ for every edge $e\in \overline{E}$. We characterize $IR$-insensitive bipartite graphs and give a constructive characterization of graphs $G$ for which the addition of any edge decreases $IR(G)$. We also demonstrate the existence of a wide class of graphs $G$ containing a pair of non-adjacent vertices $u,v$ such that $IR(G+uv)>IR(G)$.