Distance Irredundance in Graphs: Complexity Issues

Abstract

Let $n\ge 1$ be an integer. The closed $n$-neighborhood $N_n[u]$ of a vertex $u$ in a graph $G=(V,E)$ is the set of vertices $\{v|d(u,v)\le n\}$. The closed $n$-neighborhood of a set $X$ of vertices, denoted by $N_n[X]$, is the union of the closed $n$-neighborhoods $N_n[v]$ of vertices $u\in X$. For $X\subseteq V(G)$, if $N_n[x]–N_n[X–\{u\}]=\mathrm{\varnothing }$, then $u$ is said to be $n$-redundant in $X$. A set $X$ containing no $n$-redundant vertex is called $n$-irredundant. The $n$-irredundance number of $G$, denoted by $i{r}_n(G)$, is the minimum cardinality taken over all maximal $n$-irredundant sets of vertices of $G$. The upper $n$-irredundance number of $G$, denoted by $I{R}_n(G)$, is the maximum cardinality taken over all maximal $n$-irredundant sets of vertices of $G$. In this paper we show that the decision problem corresponding to the computation of $i{r}_n(G)$ for bipartite graphs $G$ is NP-complete. We then prove that this also holds for augmented split graphs. These results extend those of Hedetniemi, Laskar, and Pfaff (see [7]) and Laskar and Pfaff (see [8]) for the case $n=1$. Lastly, applying the general method described by Bern, Lawler, and Wong (see [1]), we present linear algorithms to compute the $2$-irredundance and upper $2$-irredundance numbers for trees.