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

G-2001-29

Variable Neighborhood Search for Extremal Graphs 8: Variations on Graffiti 105

, et

Graffiti's conjecture 105 states that for any tree the range of transmissions of distance is greater than or equal to the range of degrees. After using the AutoGraphiX system to find families of extremal graphs, we show that this conjecture is true and that the bound is attained if and only if the tree is a star. Adding constraints on the maximum degree leads to two further bounds, for which extremal graphs are characterized. A general bound on the range of transmissions of a tree as a function of the order and the maximum degree is then provided. Finally, a sufficient condition for the initial conjecture to hold in connected graphs is given, as well as several families of such graphs for which it is not the case.

, 17 pages