Automated Results and Conjectures on Average Distance in Graphs


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


Automated results and conjectures on average distance in graph
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