### G-2012-27

# Open Problems on Graph Eigenvalues Studied with AutoGraphiX

## Mustapha Aouchiche, Gilles Caporossi, and Pierre Hansen

Since the late forties of the last century, methods of operations research have been extensively used to solve problems in graph theory, and graph theory has been extensively used to model operations research problems and to solve optimization problems on graphs, *e.g.*, shortest paths and network flow problems. More recently, methods of operations research and artificial intelligence have been used to advance graph theory per se, *i.e.*, to find conjectures on graph theory invariants, to refute such conjectures and in some cases to find automated proofs or ideas of proofs. Among other systems, the AutoGraphiX system was developed since 1997 at GERAD (Montreal) by the present authors.

*n*vertices. The fourth problem concerns the maximization of the energy (the sum of the absolute values of the eigenvalues) of a connected graph with fixed numbers of vertices and of cycles. We present a brief survey of the papers on or in connection with these problems, and give some new partial results.

Published **May 2012**
,
21 pages