Distance Irredundance in Graphs: Complexity Issues

Let \(n \geq 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) \leq 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\}] = \emptyset\), 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 \(ir_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 \(IR_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 \(ir_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.