Please use this identifier to cite or link to this item: http://hdl.handle.net/10646/3381
Title: Average distance and edge-connectivity I
Authors: Dankelmann, Peter
Mukwembi, Simon
Swart, Henda C
metadata.dc.contributor.authoremail: simonmukwembi@gmail.com
metadata.dc.type: Article
Keywords: Plesnik
verticesof G
Issue Date: 15-Jan-2015
Publisher: Society for Industrial and Applied Mathematics
Citation: Dankelmann, P., Mukwembi, S., & Swart, H. C. (2008). Average distance and edge-connectivity I. SIAM Journal on Discrete Mathematics, 22 (1), 92-101.
Abstract: The average distance $\mu(G)$ of a connected graph G of order n is the average of the distances between all pairs of vertices of G. We prove that if G is a $\lambda$-edge-connected graph of order n, then the bounds $\mu(G) \le 2n/15+9$ if $\lambda=5,6$, $\mu(G) \le n/9+10$ if $\lambda=7$, and $\mu(G) \le n/(\lambda+1)+5$ if $\lambda \ge 8$ hold. Our bounds are shown to be best possible, and our results solve a problem of Plesník
Description: The results in this paper are part of the second author’s PhD thesis.
URI: http://hdl.handle.net/10646/3381
ISSN: 1095-7200
Appears in Collections:Department of Mathematics Staff Publications

Files in This Item:
File Description SizeFormat 
Mukwembi_Average_distance_and_Edge_Connectivity_II.pdfThe results in this paper are part of the second author’s PhD thesis.305.79 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.