Automated Results and Conjectures on Average Distance in Graphs
Mustapha Aouchiche, Pierre Hansen · Birkhäuser Basel eBooks · 2006
Using the AutoGraphiX 2 system, a systematic study is made on generation and proof of relations of the form $$ \underline b _n \leqslant \bar l \oplus i \leqslant \bar b_n $$ where \( \bar 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 \( \bar b_n \) are best possible lower and upper bounds, functions of the order n of G and ⊕ ∈ −, + ×, /. 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.