Group for Research in Decision Analysis

# Variable Neighborhood Search for Extremal Graphs. 19. Further Conjectures and Results about the Randic Index

## Mustapha Aouchiche, Pierre Hansen, and Maolin Zheng

The AutoGraphiX research program led to a new type of application of metaheuristics in graph theory, i.e., finding conjectures on graph invariants by obtaining with a generic heuristic based on Variable Neighborhood Search, a series of extremal or near-extremal graphs, then studying them with data mining techniques. We report here on some of the results so obtained. Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form $lb_n \leq R \oplus i \leq ub_n$ where $R$ denotes the Randic index of a graph G = (V,E), $i$ another invariant among maximum, minimum and average degree, $\Delta, \delta$ and $d$, diameter D, girth g, algebraic and node connectivity, $a$ and $\nu$, denotes one of the four operations $+, -, \times, /$, $lb_n$ and $ub_n$ lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). Conjectures are obtained in 51 out of 56 cases, 28 of which are proved automatically, 19 are proved by hand, 7 remain open and only one was refuted.

, 22 pages