Variable Neighborhood Search for Extremal Graphs. 17. Further Conjectures and Results about the Index

, , and

BibTeX reference

The AutoGraphiX 2 system is used to compare the index of a graph G with a number of other graph theoretical invariants, i.e., chromatic number, maximum, minimum and average degree, diameter, radius, average distance, independence and domination numbers. In each case, best possible lower and upper bounds, in terms of the order of G, are sought for sums, differences, ratios and products of the index and another invariant. There are 72 cases altogether: in 7 cases known results were reproduced, in 32 cases immediate results were obtained and automatically proved by the system, conjectures were obtained in 20 cases, of which 11 were proved in 2 theorems and 9 propositions, and 9 remain open. Further conjectures were refuted in 6 cases and no results could be derived in 7 cases.

, 25 pages

This cahier was revised in January 2007

Research Axis

Research applications


Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
, , and
Discussiones Mathematicae : Graph Theory, 29, 15–37, 2009 BibTeX reference