AVERAGE DISTANCE AND EDGE-CONNECTIVITY II

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 for a 3-edge-connected graph $G$ of order $n$ the inequality $\mu(G)\le{n}/{6}+24$ on the average distance holds. Our bound is shown to be best poss...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2008-01, Vol.21 (4), p.1035-1052
Main Authors: DANKELMANN, Peter, MUKWEMBI, Simon, SWART, Henda C
Format: Article
Language:English
Subjects:
Algebra
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Connectivity
Exact sciences and technology
Graph theory
Graphs
Information retrieval. Graph
Mathematics
Neighborhoods
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 for a 3-edge-connected graph $G$ of order $n$ the inequality $\mu(G)\le{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].
ISSN:0895-4801
1095-7146
DOI:10.1137/06065653X