Average distance, minimum degree, and irregularity index
Simon Mukwembi · Discrete Mathematics · 2023
Let G=(V,E) be a connected graph of order n. The distance, dG(x,y), between vertices x and y in G is defined as the length of a shortest x-y path in G. The average distance, μ(G), of G is defined as μ(G)=(n2)−1∑{x,y}⊆VdG(x,y). We give an upper bound on the average distance of a connected graph of given order and minimum degree where irregularity index is prescribed. Our results are a strengthening of the classical theorems by Kouider and Winkler (1997) [9] and by Dankelmann and Entringer (2000) [5] on average distance and minimum degree if the number of distinct terms in the degree sequence of the graph is prescribed.