Average distance and edge-connectivity II

Peter Dankelmann; Simon Mukwembi; Henda C. Swart

doi:10.1137/06065653X

Average distance and edge-connectivity II

Peter Dankelmann, Simon Mukwembi, Henda C. Swart

University of KwaZulu-Natal

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

Abstract

The average distance μ(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 for a 3-edge-connected graph G of order n the inequality μ(G) ≤ n/6 + 24 on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesník [J. Graph Theory, 8 (1984), pp. 1-24].

Original language	English
Pages (from-to)	1035-1052
Number of pages	18
Journal	SIAM Journal on Discrete Mathematics
Volume	21
Issue number	4
DOIs	https://doi.org/10.1137/06065653X
Publication status	Published - 2007
Externally published	Yes

Keywords

Average distance
Distance
Edge-connectivity

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/06065653X

Cite this

@article{da79042d5d5e49b2929fb03eff88613e,

title = "Average distance and edge-connectivity II",

abstract = "The average distance μ(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 for a 3-edge-connected graph G of order n the inequality μ(G) ≤ n/6 + 24 on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesn{\'i}k [J. Graph Theory, 8 (1984), pp. 1-24].",

keywords = "Average distance, Distance, Edge-connectivity",

author = "Peter Dankelmann and Simon Mukwembi and Swart, {Henda C.}",

year = "2007",

doi = "10.1137/06065653X",

language = "English",

volume = "21",

pages = "1035--1052",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Average distance and edge-connectivity II

AU - Dankelmann, Peter

AU - Mukwembi, Simon

AU - Swart, Henda C.

PY - 2007

Y1 - 2007

N2 - The average distance μ(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 for a 3-edge-connected graph G of order n the inequality μ(G) ≤ n/6 + 24 on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesník [J. Graph Theory, 8 (1984), pp. 1-24].

AB - The average distance μ(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 for a 3-edge-connected graph G of order n the inequality μ(G) ≤ n/6 + 24 on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesník [J. Graph Theory, 8 (1984), pp. 1-24].

KW - Average distance

KW - Distance

KW - Edge-connectivity

UR - http://www.scopus.com/inward/record.url?scp=56649116078&partnerID=8YFLogxK

U2 - 10.1137/06065653X

DO - 10.1137/06065653X

M3 - Article

AN - SCOPUS:56649116078

SN - 0895-4801

VL - 21

SP - 1035

EP - 1052

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

Average distance and edge-connectivity II

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this