Diametral broadcast graphs

作者：Grigoryan Hayk^*; Harutyunyan Hovhannes A

来源：Discrete Applied Mathematics, 2014, 171: 53-59.

DOI：10.1016/j.dam.2014.02.005

• Broadcasting
• Minimum broadcast graphs
• Diametral broadcast graphs
• Diametral broadcast trees
• Diametral broadcast function

This paper studies the family of graphs with broadcast time equal to their diameter. The diametral broadcast graph (dbg) problem is to answer the question whether for a given n and d a graph on n vertices can be constructed whose diameter and broadcast time are equal to d. This paper presents several dbg constructions. Together, they solve the dbg problem for all the possible combinations of values of n and d. We also define the diametral broadcast function DB(n, d) as the minimum possible number of edges in a dbg on n vertices and diameter d. We describe all the trees on n vertices with diametral broadcast time. These trees give the exact value for DB(n, d) when tree based dbg construction is possible. For the general case we give an upper bound on DB(n, d).

• 出版日期2014-7-10