Group for Research in Decision Analysis


Variable Neighborhood Search for Extremal Graphs. 20. Automated Comparison of Graph Invariants

, , and

A graph invariant is a function of a graph G which does not depend on labeling of G’s vertices or edges. An algebraic expression of one or several graph invariants is itself an invariant. Graph theory is replete with theorems about graph invariants, which are either algebraic, i.e., equalities or inequalities involving such invariants, or structural, i.e., characterizations of which families of graphs are extremal for a given invariant, that is give it maximum or minimum values. Both types of results can be conjectured by the system AutoGraphiX 2 (AGX 2), in an automated way, or, in some carefully distinguished cases, in an assisted way. We report here on a systematic comparison of 20 graph invariants: for each pair of them, AGX 2 considers the four operations +,−,×, / and derives best possible lower and upper bounding functions of the number of vertices, as well as extremal graphs. Out of 1520 cases, AGX 2 recognizes 37 known results, derives automatically algebraic and corresponding structural conjectures in 1260 cases (841 of which are proved automatically), and structural conjectures only in 168 more cases, from which algebraic conjectures could be derived by hand in 86 cases. No results were obtained in 55 cases. Manual or assisted proofs have been obtained in 394 cases, 22 conjectures were refuted and 171 conjectures remain open. Many examples are given. AGX 2 is also compared to the three operational systems GRAPH, GRAFFITI and HR.

, 24 pages

This cahier was revised in January 2007