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

# Automated Results and Conjectures on Average Distance in Graphs

## Mustapha Aouchiche et Pierre Hansen

Using the AutoGraphiX 2 system, a systematic study is made on generation and proof of relations of the form

$\underline{b}_n \leq \overline{l} \oplus i \leq \overline{b}_n$

where $\overline{l}$ denotes the average distance between distinct vertices of a connected graph G, i one of the invariants: diameter, radius, girth, maximum, average and minimum degree, $\underline{b}_n$ and $\overline{b}_n$ are best possible lower and upper bounds, functions of the order n of G and $\oplus \in \{ -,+ \times, /\}$. In 24 out of 48 cases simple bounds are obtained and proved by the system. In 21 more cases, the system provides bounds, 16 of which are proved by hand.

, 23 pages

Ce cahier a été révisé en novembre 2005