An alternative definition of the k-irredundance
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\).
- (k,r)-Irredundant sets in graphs
- scientific article; zbMATH DE number 3977049
- scientific article; zbMATH DE number 2188352
- Irredundance and Maximum Degree in Graphs
- Total irredundance in graphs
- scientific article; zbMATH DE number 4055676
- scientific article; zbMATH DE number 140135
- Irredundance saturation number of a graph
- scientific article; zbMATH DE number 5777938
- A note on the irredundance number after vertex deletion
This page was built for publication: An alternative definition of the \(k\)-irredundance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2566906)
