Finding Conjectures in Graph Theory with AutoGraphiX

Pierre Hansen
GERAD and HEC Montréal

Mustapha Aouchiche
GERAD and HEC Montréal

Gilles Caporossi
GERAD and HEC Montréal



Content: Computers have been used extensively to solve exactly or approximately a large variety of combinatorial otimization problems defined on graphs. It has also been noticed, in the last two decades, that computers can be used to advance graph theory {\it per se}. Several systems (e.g., Graph, Graffiti, AutoGraphiX, GrapHedron, GrInvIn, Nauty and Vega) have been proposed for that purpose. In this paper, we discuss the system AutoGraphiX developped at GERAD, Montreal, since 1997. Results of systematic experiments with conjectures of AGX Form~1: {\it i.e.} $$ (\mathcal{F}_{inf}) \quad L_n \le i_1 \otimes i_2 \le U_n \quad (\mathcal{F}_{sup}) $$ where $i_1$ and $i_2$ are two graph invariants; $\otimes$ is one of $-, +, /$ or $\times$; $L_n, U_n$ are lower and upper bounds as functions of $n$; and $\mathcal{F}_{inf}$ and $\mathcal{F}_{sup}$ are families of extremal graphs associated with these bounds, are discussed. Some conjectures with a more general form and their posterity are also considered.

Back to all abstracts