Broadcasting in Odd Graphs

Broadcasting refers to the process of information dissemination in a communication network whereby a message is to be sent from a single originator to all members of the network, subject to the restriction that a member may participate in only one message transfer during a given time unit. In this paper we present a family of broadcasting schemes over the odd graphs, \(O_{n+1}\). It is shown that the broadcast time of \(O_{n+1}\), \(b(O_{n+1})\), is bounded by \(2n\). Moreover, the conjecture that \(b(O_{n+1}) = 2n\) is put forward, and several facts supporting this conjecture are given.