# 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

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**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.