Back

G-2005-08

Automated Results and Conjectures on Average Distance in Graphs

and

BibTeX reference

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

This cahier was revised in November 2005

Research Axes

Research applications

Publication

Automated results and conjectures on average distance in graph
and
J.A. Bondy, J. Fonlupt, J.L. Fouquet, J.C. Fournier, L. Ramirez-Alfonsin (eds.), Game Theory in Paris: Special Volume in Memory of Claude Berge, 21–36, 2007 BibTeX reference