On the sum of all distances in a graph or digraph 论文
1984Journal of Graph Theory引用 258
Advanced Graph Theory ResearchInterconnection Networks and SystemsVLSI and FPGA Design Techniques
摘要
Abstract 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 C n . 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.