Automated Results and Conjectures on Average Distance in Graphs


référence BibTeX

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

Axes de recherche

Applications de recherche


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 référence BibTeX