Some minimum gossip graphs
Roger Labahn · Networks · 1993
Abstract What is the minimum number of edges that a graph on n vertices must have to allow gossiping by bidirectional telephone calls within ⌈log 2 n ⌉ rounds? Besides general estimates, this question is finally answered for integers of the form n = 2 p − 2 ( p ≥ 3) or n = 2 p − 4 ( p ≥ 6), and for n = 10, 12. Moreover, for n = 14, we prove the uniqueness of such a graph. © 1993 by John Wiley & Sons, Inc.