Combinatorics Probability Computing · 1997 · 19 citations · 2 references
Natural SciencesComputer ScienceMathematicsCombinatoricsSet TheoryGraph AlgorithmsGraph TheoryCardinality EstimationSet Cardinality
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 2 n /3Δ. This substantially improves a bound by Bollobás and Cockayne [1]. The class of graphs which attain this bound is characterised.
2