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.