A note on the irredundance number after vertex deletion
Let \(A\) be a set of vertices of a graph \(G\). A vertex \(x\) of \(A\) is said to be irredundant in \(A\) if either \(x\) is isolated in \(A\) or admits at least one \(A\)-private neighbor, i.e., a neighbor \(x'\) in \(V-A\) which is adjacent to no other vertex of \(A\). A set \(A\) is irredundant in \(G\) if each of its vertices is irredundant in \(A\). Denote by \(\text{ir} (G)\) the minimum cardinality of a maximal irredundant set of \(G\). J. Topp conjectured that \(\text{ir}(G-v)\geq\text{ir}(G)-1\) for every vertex \(v\) of \(G\). The author shows that for every graph \(G\) and every vertex \(v\) of \(G\) if \(\text{ir} (G-v) \geq 2\) then \(\text{ir} (G) \leq 2 \text{ir} (G- v)-1\) and this bound is sharp.
scientific article; zbMATH DE number 473114