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

Bounding Average Distance Using Order and Minimum Degree

Mustapha Aouchiche et Pierre Hansen

Upper bounds on the average distance $$\overline{l}$$ between pairs of vertices of a connected graph with given order $$n$$ and minimum degree $$\delta$$ are studied. The AutoGraphiX system for conjecture making is used to generate such bounds when the minimum degree is at least 2, 3, 4 or 5. A sharp bound is proved when $$\delta \ge 2$$ and conjectures are provided in the remaining three cases. Two more conjectures are given for particular cases, namely, when $$n = (\delta +1)k$$ and $$n=(\delta +1)k +2$$ for some integer $$k \ge 2$$.

, 16 pages