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

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

## Mustapha Aouchiche, Pierre Hansen et Maolin Zheng

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 matching number $\mu$ and the index $\lambda_1$, $\oplus$ 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 14 out of 16 cases, 6 of which are proved automatically, 7 are proved by hand and one remains open.

, 16 pages