Premium
On the sum of all distances in a graph or digraph
Author(s) -
Plesník Ján
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080102
Subject(s) - combinatorics , digraph , mathematics , independence number , graph , discrete mathematics
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.