Premium
Some minimum gossip graphs
Author(s) -
Labahn Roger
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230416
Subject(s) - gossip , combinatorics , uniqueness , graph , mathematics , discrete mathematics , computer science , psychology , social psychology , mathematical analysis
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.