On the maximum value of the eccentric distance sums of cubic transitive graphs

摘要

Let Γ be a simple connected graph with vertex set V(Γ). The eccentric distance sum (EDS for short) of Γ is defined as ξd(Γ)=∑v∈V(Γ)εΓ(v)DΓ(v), where ɛΓ(v) is the eccentricity of a vertex v and DΓ(v) is the sum of all distances from v to other vertices. In the paper Li and Wu [11], the strict upper bound on ξd(Γ) among the k-connected graphs Γ with an integer k even were given, and proposed an open question: the corresponding problem on k-connected graphs with k odd. In this paper, first, we divide cubic transitive graphs into two cases: super-connectedness and non-super-connectedness, and characterized non-super-connected cubic transitive graphs, filling the gaps in this field. Then, by using the characterization, we show the upper bound on EDS among (3-connected) cubic transitive graphs of order n and characterize the extremal graphs: the ladders when n≡0(mod4) and the ladders or the Möbius ladders when n≡2(mod4). Finally, we conclude the paper with conjectures about the upper bound on EDS of k-connected graphs with odd integer k ≥ 3.