G-2006-27
Variable Neighborhood Search for Extremal Graphs. 19. Further Conjectures and Results about the Randic Index
, et référence BibTeX
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
where
denotes the Randic index of a graph G = (V,E),
another invariant among
maximum, minimum and average degree,
and
, diameter D, girth g, algebraic
and node connectivity,
and
,
denotes one of the four operations
,
and
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.
Paru en avril 2006 , 22 pages