Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system

摘要

Finding extremal graphs for expressions involving one or more invariants is viewed as a problem of combinatorial optimization. The recent Variable Neighborhood Search metaheuristic is used to solve it. Neighborhoods are defined by addition, removal or exchange of edges, removal of pendant vertices and similar transformations. First results, obtained with the system AutoGraphiX, are presented: many extremal graphs are determined, three conjectures from Graffiti are refuted, other conjectures are sharpened and new ones proposed.