Irredundance and Maximum Degree in Graphs
E. J. Cockayne, Christina M. Mynhardt · Combinatorics Probability Computing · 1997
It is proved that the smallest cardinality among the maximal irredundant sets in an n–vertex graph with maximum degree Δ([ges ]2) is at least 2n/3Δ. This substantially improves a bound by Bollobás and Cockayne [1]. The class of graphs which attain this bound is characterised.