论文标题
定向和无向图中的接近和远程性
Proximity and Remoteness in Directed and Undirected Graphs
论文作者
论文摘要
让$ d $成为牢固连接的挖掘物。顶点$ v $ $ d $的平均距离$ \barσ（v）$是从$ v $到$ d $的所有其他顶点的算术平均值。偏远$ρ（d）$和接近$π（d）的$ d $是最大值和最小值$ d $的平均距离的最小值。我们在$π（d）$和$ρ（d）$上获得了尖锐的上和下限，这是$ n $ $ d $的订单的函数，并描述了所有界限的极端挖掘。我们还获得了强大的比赛的界限。我们表明，对于强大的比赛$ t $，当时我们有$π（t）=ρ（t）$，并且仅当$ t $是常规的。由于这个结果，可以猜想每个强大的Digraph $ d $，$π（d）=ρ（d）$都是常规的。我们提出了一个无限的不规则强度挖掘$ d $的家族，使得$π（d）=ρ（d）。$我们也描述了这样一个无向图的家庭。
Let $D$ be a strongly connected digraph. The average distance $\barσ(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.
