Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number Original Research Article

A set of vertices image in a graph image is independent if no neighbor of a vertex of image belongs to image. The independence number image is the maximum cardinality of an independent set of image. A series of best possible lower and upper bounds on image and some other common invariants of image are obtained by the system AGX 2, and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number.