Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance

A set of vertices SS in a graph GG is independent if no neighbor of a vertex of SS belongs to SS. A set of vertices UU in a graph GG is irredundant if each vertex vv of UU has a private neighbor, which may be vv itself, i.e., a neighbor of vv which is not a neighbor of any other vertex of UU. The independence number αα (resp. upper irredundance number IRIR) is the maximum number of vertices of an independent (resp. irredundant) set of GG. In previous work, a series of best possible lower and upper bounds on αα and some other usual invariants of GG were obtained by the system AGX 2, and proved either automatically or by hand. These results are strengthened in the present paper by systematically replacing αα by IRIR. The resulting conjectures were tested by AGX which could find no counter-example to an upper bound nor any case where a lower bound could not be shown to remain tight. Some proofs for the bounds on αα carry over. In all other cases, new proofs are provided.