A study of the variable neighbourhood of certain extreme graphs

The AutoGraphiX system (AGX1 and AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form bn ⩽ g ⊕ i ⩽ bn where g denotes the girth (or length of the smallest cycle) of a graph G=(V, E), i another invariant among independence number, radius, diameter, minimum, average or maximum degree, bn and bn best possible functions of the order n of G, and ⊕ denotes one of the four operations +, −, ×, /. 48 such conjectures are obtained: the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.