Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants

Mustapha Aouchiche, Gilles Caporossi, Pierre Hansen

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)


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 value, 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 coses, 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.

Original languageEnglish
Pages (from-to)365-384
Number of pages20
Issue number2
Publication statusPublished - 2007
Externally publishedYes

ASJC Scopus subject areas

  • General Chemistry
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants'. Together they form a unique fingerprint.

Cite this