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
WorldCat Link
Citation
Beezer, R.A, J.E Riegsecker, and B.A Smith. "Using Minimum Degree to Bound Average Distance." Discrete Mathematics. 226 (2001): 365-371. Print.