Let $D$ be a strongly connected digraph. The average distance
$\sigma(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the
distances from $v$ to all other vertices of $D$. The remoteness $\rho(D)$ and
proximity $\pi(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 $\pi(D)$ and $\rho(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
$\pi(T)=\rho(T)$ if and only if $T$ is regular. Due to this result, one may
conjecture that every strong digraph $D$ with $\pi(D)=\rho(D)$ is regular. We
present an infinite family of non-regular strong digraphs $D$ such that
$\pi(D)=\rho(D).$ We describe such a family for undirected graphs as well.
Описание
Proximity and Remoteness in Directed and Undirected Graphs
%0 Generic
%1 ai2020proximity
%A Ai, Jiangdong
%A Gerke, Stefanie
%A Gutin, Gregory
%A Mafunda, Sonwabile
%D 2020
%K 4330 graph_seminar network_analysis proximity
%T Proximity and Remoteness in Directed and Undirected Graphs
%U http://arxiv.org/abs/2001.10253
%X Let $D$ be a strongly connected digraph. The average distance
$\sigma(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the
distances from $v$ to all other vertices of $D$. The remoteness $\rho(D)$ and
proximity $\pi(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 $\pi(D)$ and $\rho(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
$\pi(T)=\rho(T)$ if and only if $T$ is regular. Due to this result, one may
conjecture that every strong digraph $D$ with $\pi(D)=\rho(D)$ is regular. We
present an infinite family of non-regular strong digraphs $D$ such that
$\pi(D)=\rho(D).$ We describe such a family for undirected graphs as well.
@misc{ai2020proximity,
abstract = {Let $D$ be a strongly connected digraph. The average distance
$\bar{\sigma}(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the
distances from $v$ to all other vertices of $D$. The remoteness $\rho(D)$ and
proximity $\pi(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 $\pi(D)$ and $\rho(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
$\pi(T)=\rho(T)$ if and only if $T$ is regular. Due to this result, one may
conjecture that every strong digraph $D$ with $\pi(D)=\rho(D)$ is regular. We
present an infinite family of non-regular strong digraphs $D$ such that
$\pi(D)=\rho(D).$ We describe such a family for undirected graphs as well.},
added-at = {2020-01-29T16:14:58.000+0100},
author = {Ai, Jiangdong and Gerke, Stefanie and Gutin, Gregory and Mafunda, Sonwabile},
biburl = {https://www.bibsonomy.org/bibtex/25e874fab2633881e810320b1db779b95/j.c.m.janssen},
description = {Proximity and Remoteness in Directed and Undirected Graphs},
interhash = {ca64c5c08b2d89f0f9e2657c31e9826f},
intrahash = {5e874fab2633881e810320b1db779b95},
keywords = {4330 graph_seminar network_analysis proximity},
note = {cite arxiv:2001.10253},
timestamp = {2020-01-29T16:14:58.000+0100},
title = {Proximity and Remoteness in Directed and Undirected Graphs},
url = {http://arxiv.org/abs/2001.10253},
year = 2020
}