Proximity and Remoteness in Directed and Undirected Graphs
share
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.
READ FULL TEXT
