Back

# Bounding Average Distance Using Order and Minimum Degree

## Mustapha Aouchiche and Pierre Hansen

BibTeX reference

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

### Publication

Bounding average distance using order and minimum degree
and
Graph Theory Notes of New York, LVI, 21–29, 2009 BibTeX reference