Bounds for eccentricity-based parameters of graphs

2023/04/23 by Yunfang Tang, Xuli Qi, Tang, Yunfang +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2304.11537

openalex publication_date 2023/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The eccentricity of a vertex u in a graph G, denoted by e_G(u), is the maximum distance from u to other vertices in G. We study extremal problems for the average eccentricity and the first and second Zagreb eccentricity indices, denoted by σ₀(G), σ₁(G), and σ₂(G), respectively. These are defined by σ₀(G)=(1)/(|V(G)|)∑_{u∈ V(G)}e_G(u), σ₁(G)=∑_{u∈ V(G)}e_G²(u), and σ₂(G)=∑_{uv∈ E(G)}e_G(u)e_G(v). We study lower and upper bounds on these parameters among n-vertex connected graphs with fixed diameter, chromatic number, clique number, or matching number. Most of the bounds are sharp, with the corresponding extremal graphs characterized.

Related

• Average eccentricity, minimum degree and maximum degree in graphs
• On the extremal properties of the average eccentricity
• The average eccentricity of a graph with prescribed girth
• Total eccentricity index of graphs with fixed number of pendant or cut vertices
• On the difference between the eccentric connectivity index and eccentric\n distance sum of graphs