Group for Research in Decision Analysis


Finding conjectures in graph theory with AutoGraphiX

, , , , and

Graph theoretical heuristics are used extensively in many fields to solve approximately large scale optimization problems. Graph theoretical heuristics can also be used to advance graph theory per se, i.e., to refute, find, corroborate, prove or give ideas of proof of conjectures on graph invariants, i.e., numerical quantities that not depend on vertex or edge labeling. In this paper, we present and discuss the AutoGraphiX system which finds automatically or in some cases, interactively conjectures in graph theory. We consider in particular conjectures on pairs of a set of 20 graph invariants, which gives rise to 1520 cases.

, 22 pages