A note on the irredundance number after vertex deletion
type: Item
instance of: scholarly article
title: A note on the irredundance number after vertex deletion
zbMATH Open document ID: 0791.05095
DOI: 10.1016/0012-365X(93)90536-3
author: Odile Favaron
published in: Discrete Mathematics
publication date: 1994-06-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 473114
zbMATH Keywords: irredundance number
zbMATH Keywords: domination
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
Wikidata QID: Q127549562
description: scientific article; zbMATH DE number 473114