Abstract
Let n ≥ 1 he an integer. The closed n-neighborhood Nn[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 Nn[X], is the union of the closed n-neighborhoods Nn[u] of vertices u in X. For x ∈ X ⊆ V (G), if Nn[x] - Nn[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 irn(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 IRn(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 irn(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