Average distance in weighted graphs

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We consider the following generalisation of the average distance of a graph. Let G be a connected, finite graph with a nonnegative vertex weight function c. Let N be the total weight of the vertices. If N≠0,1, then the weighted average distance of G with respect to c is defined by μc(G)=N2-1∑u,v⊆Vc(u)c(v)dG(u,v), where dG(u,v) denotes the usual distance between u and v in G. If c(v)=1 for all vertices v of G, then μc(G) is the ordinary average distance. We present sharp bounds on μc for trees, cycles, and graphs with minimum degree at least 2. We show that some known results for the ordinary average distance also hold for the weighted average distance, provided that each vertex has weight at least 1.

Original languageEnglish
Pages (from-to)12-20
Number of pages9
JournalDiscrete Mathematics
Issue number1
Publication statusPublished - 6 Jan 2012
Externally publishedYes


  • Average distance
  • Distance
  • Weighted graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Average distance in weighted graphs'. Together they form a unique fingerprint.

Cite this