Retour

G-2005-08

Automated Results and Conjectures on Average Distance in Graphs

et

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

Publication

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