Minimum linear gossip graphs and maximal linear \((\Delta,k)\)-gossip graphs (Q2764998)

A minimum linear gossip graph is a graph or network with the minimum number of links in which gossiping can be completed in minimum time under the linear-cost model. For a minimum linear gossip graph with an even number of nodes, it is shown that its structure is independent of the relative values of the start-up and unit propagation times, and this is not true when the number of nodes is odd. Four infinite families of minimum linear gossip graphs are presented. Also, the paper gives minimum linear gossiping graphs for all even numbers of nodes \(n\leq 32\) except \(n= 22\).NEWLINENEWLINENEWLINEA linear \((\Delta,k)\)-gossip graph is a graph with maximum degree \(\Delta\) in which gossiping can be completed in \(k\) rounds with minimum propagation time. The paper presents three infinite families of maximal linear \((\Delta, k)\)-gossip graphs. It is shown that not all-minimum broadcast graphs are maximal linear \((\Delta,k)\)-gossip graphs.