An alternative definition of the \(k\)-irredundance (Q2566906): Difference between revisions

Given a graph \(G=(V, E)\) and an integer \(k\geq 1\), \textit{M. S. Jacobson} et al. [Ars Comb. 29B, 151-160 (1990; Zbl 0743.05063)] define a \(k\)-irredundant set as a subset \(S\) of \(V\) such that, for all \(x\in S\), either \(x\) has fewer than \(k\) neighbors in \(S\) or \(x\) has a neighbor \(x'\in V\setminus X\) adjacent to exactly \(k\) vertices of \(S\). This concept generalizes the ordinal irredundance, and the minimum and maximum cardinality of a \(k\)-irredundant set of \(G\) satisfy certain inequalities when comparing with other related graph parameters. However, this generalization of irredundance presents two inconveniences: First, a subset of a \(k\)-irredundant set is not necessarily again \(k\)-irredundant, hence a single vertex extension is not sufficient for determining maximality of \(k\)-irredundant sets. Second, a \(k\)-irredundant set is not necessarily \((k+1)\)-irredundant, hence for \(k_1\leq k_2\) the maximum cardinality of a \(k_1\)-irredundant set is not necessarily at most the maximum cardinality of a \(k_2\)-irredundant set. For this reasons, the author proposes a slightly different definition of \(k\)-irredundance avoiding these two inconveniences while keeping the main properties of those due to Jacobson et al. Her definition is as follows: A subset \(S\) of \(V\) is \(k\)-irredundant if, for all \(x\in S\), either \(x\) has fewer than \(k\) neighbors in \(S\) or \(x\) has a neighbor \(x'\in V\setminus S\) adjacent to at most \(k\) vertices of \(S\).