On the sum of all distances in a graph or digraph
On the sum of all distances in a graph or digraph
复制标题
DOI：
10.1002/jgt.3190080102
复制
发表时间：
1984-03
期刊：
影响因子：
--
通讯作者：
J. Plesník
中科院分区：
文献类型：
--
作者：
J. Plesník
图或有向图G的传输量是G中所有距离的和。对若干类图和有向图，收集并扩展了传输量的严格界限。例如，在n阶的2连通或2边连通图中，最大传输仅通过循环Cn来实现。传输对直径或半径的独立性显示。对一些相关算法问题的np -硬度也作了讨论。
The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2-connected or 2-edge-connected graphs of order n, the maximal transmission is realized only by the cycle Cn. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP-hardness of some related algorithmic problems.