Distance irredundance in graphs: Complexity issues

Johannes H. Hattingh, Michael A. Henning, Jacobus L. Walters

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 languageEnglish
Pages (from-to)3-22
Number of pages20
JournalArs Combinatoria
Publication statusPublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Distance irredundance in graphs: Complexity issues'. Together they form a unique fingerprint.

Cite this