Bounding Average Distance Using Order and Minimum Degree


BibTeX reference

Upper bounds on the average distance \(\overline{l}\) between pairs of vertices of a connected graph with given order \(n\) and minimum degree \(\delta\) are studied. The AutoGraphiX system for conjecture making is used to generate such bounds when the minimum degree is at least 2, 3, 4 or 5. A sharp bound is proved when \(\delta \ge 2\) and conjectures are provided in the remaining three cases. Two more conjectures are given for particular cases, namely, when \(n = (\delta +1)k\) and \(n=(\delta +1)k +2\) for some integer \(k \ge 2\).

, 16 pages

Research Axis

Research applications


Bounding average distance using order and minimum degree
Graph Theory Notes of New York, LVI, 21–29, 2009 BibTeX reference