### G-2005-40

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

## , , and BibTeX reference

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.

Published **April 2005**
,
24 pages

This cahier was revised in **January 2007**