Title

Using minimum degree to bound average distance

Document Type

Article

Publication Date

2001

Publication Title

Discrete Mathematics

Department

Mathematics and Computer Science

Abstract

We show the average distance mu of a connected graph with n vertices, e edges and minimum degree d satisfies [(n+1)n(n-1)-2e/d+1]/n(n-1) This improves conjectures of the computer program Graffti (Fajtlowicz, Written on the wall, Conjectures made by program Graffiti, University of Houston, 1990), and He and Li (Math. Appl. 4 (1991) 28-34) and the results of Kouider and Winkler (J. Graph Theory 25 (1997) 95 -99). The bound is sharp since complete graphs yield equality.

Volume

226

Issue

13

pp.

365-371

ISSN

0012-365X

Link to Full Text

Share

COinS