Using minimum degree to bound average distance
type: Item
instance of: scholarly article
title: Using minimum degree to bound average distance
zbMATH Open document ID: 0959.05038
DOI: 10.1016/S0012-365X(00)00156-4
author: J. E. Riegsecker
author: B. A. Smith
author: Robert A. Beezer
published in: Discrete Mathematics
publication date: 2001-04-20T00:00:00Z
review text: The authors show that the average distance \(\mu\) of a connected graph with \(n\) vertices, \(e\) edges and minimum degree \(d\) satisfies \[ \mu n(n-1)\leq \left\lfloor \frac{(n+1)n(n-1)-2e}{d+1} \right\rfloor . \] This improves conjectures of the computer program Graffiti, and \textit{W. He} and \textit{S. Li} [Math. Appl. 4, No. 2, 28-34 (1991; Zbl 0891.05030)] and the results of \textit{M. Kouider} and \textit{P. Winkler} [J. Graph Theory 25, No. 1, 95-99 (1997; Zbl 0872.05011)]. The bound is attained by complete graphs.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1565954
zbMATH Keywords: average distance
zbMATH Keywords: minimum degree
zbMATH Keywords: Graffiti
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00156-4
OpenAlex ID: W2079527110
Recommended article: Mean distance and minimum degree
Recommended article: Minimum Average Distance Triangulations
Recommended article: On Approximating the Average Distance Between Points
Recommended article: Bounds for the minimum distance function
Recommended article: On min–max distance degree index
Recommended article: Average distance, minimum degree, and spanning trees
Recommended article: On eccentric distance sum and minimum degree
Recommended article: Minimum distance estimators
Recommended article: Q3444798
description: scientific article; zbMATH DE number 1565954