Groupe d’études et de recherche en analyse des décisions


Variable Neighborhood Search for Extremal Graphs. 27. Families of Extremal Graphs

, et

The AutoGraphiX system (AGX 1 and AGX 2) for interactive, and for several functions automated, graph theory, discovers conjectures of algebraic or structural form. In this paper, we focus on the later, i.e. families of extremal graphs for a series of relations between pairs of graph invariants chosen among 20 selected ones. The form of these relations generalizes that one of Nordhaus-Gaddum relations. There are 1520 cases, leading to 47 families of extremal graphs. They include many classical families but also some apparently new ones (bags, bugs, ...). Five ways to exploit these families of extremal graphs in order to enhance the performance of AutoGraphiX are studied and illustrated by examples.

, 32 pages