## Abstract

Let n ≥ 1 he 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) ≤ 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}[u] of vertices u in X. For x ∈ X ⊆ V (G), if N_{n}[x] - N_{n}[X - {x}] = ∅, then x 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 N P-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.

Original language | English |
---|---|

Pages (from-to) | 3-22 |

Number of pages | 20 |

Journal | Ars Combinatoria |

Volume | 50 |

Publication status | Published - 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- General Mathematics