On Mean Distance and Girth

2008/06/09 by Siham Bekkai, Bekkai, Siham, Mekkia Kouider +1
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #History and Theory of Mathematics #Mathematics and Applications

paper · pdf · doi:10.48550/arxiv.0806.1438

openalex publication_date 2008/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We bound the mean distance in a connected graph which is not a tree in function of its order n and its girth g. On one hand, we show that mean distance is at most (n+1)/(3)-(g(g²-4))/(12n(n-1)) if g is even and at most (n+1)/(3)-(g(g²-1))/(12n(n-1)) if g is odd. On the other hand, we prove that mean distance is at least (ng)/(4(n-1)) unless G is an odd cycle.

Related

• Mean distance on metric graphs
• The average eccentricity of a graph with prescribed girth
• Radius, Girth and Minimum Degree
• Upper Bounds on the average eccentricity of Graphs of Girth 6 and (C₄, C₅)-free Graphs
• A classification of Q-polynomial distance-regular graphs with girth 6