A lower bound for the CO-irredundance number of a graph

This paper establishes a necessary and sufficient condition for a CO-irredundant set of vertices of a graph to be maximal and shows that the smallest cardinality of a maximal CO-irredundant set in an n vertex graph with maximum degree Δ is bounded below by n/2 for Δ=2, 4n/13 for Δ=3 and 2n/(3Δ-3) for Δ⩾4. This result is best possible and extremal graphs are characterised for Δ⩾3.