2020/01/28 by Ai, Jiangdong, Gerke, Stefanie, Gutin, Gregory +1 · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.10253
Let D be a strongly connected digraph. The average distance σ(v) of a vertex v of D is the arithmetic mean of the distances from v to all other vertices of D. The remoteness ρ(D) and proximity π(D) of D are the maximum and the minimum of the average distances of the vertices of D, respectively. We obtain sharp upper and lower bounds on π(D) and ρ(D) as a function of the order n of D and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament T, we have π(T)=ρ(T) if and only if T is regular. Due to this result, one may conjecture that every strong digraph D with π(D)=ρ(D) is regular. We present an infinite family of non-regular strong digraphs D such that π(D)=ρ(D). We describe such a family for undirected graphs as well.