Distance irredundance in graphs: Complexity issues (Q2713632)

The closed \(n\)-neighbourhood \(N_n [u]\) of a vertex \(u\) in a graph \(G = (V,E)\) is the set of vertices \(\{v \mid \text{dist}(u,v)\leq n\}\). The closed \(n\)-neighbourhood \(N_n[X]\) of a set \(X\) of vertices is the union of the closed \(n\)-neighbourhoods \(N_n[u]\) of vertices \(u\) in \(X\). For \(x\in X\subseteq V(G)\), if \(N_n[x]-N_n[X-\{x\}]=\emptyset \), then \(x\) is said to be \(n\)-redundant in \(X\). A set \(X\) containing no \(n\)-redundant vertex is called \(n\)-irrendundant. The \(n\)-irredundance number of \(G\), \(\text{ir}_n(G)\), (upper \(n\)-irredundance number of \(G\), \(\text{IR}_n (G)\)) is the minimum (maximum) cardinality taken over all maximal \(n\)-irrendundant sets of vertices of \(G\). It is shown that the decision problem corresponding to the computation of ir\(_n(G)\) for bipartite graphs and augmented split graphs is NP-complete. Linear algorithms to compute the 2-irredundance and upper 2-irredundance numbers for trees are also presented.