Broadcasting in Optimal Bipartite Double Loop Graphs

Double loop graphs are extensions of the ring topology which are obtained by regularly adding 2 extra edges per vertex. An optimal graph of diameter d has the maximum possible number of vertices. The optimal structure of double loop graphs, as well as the broadcast time and an optimal broadcast scheme are known. In this paper, we define the family of bipartite double loop graphs (BDLG) G = (V, E) where V = V₀ cup V₁, V₀ cap V₁ = phi and |V₀| = |V₁|. We show that the maximum number of vertices that a BDLG of diameter d can have is 2d². We also study the broadcast problem and find that the broadcast time is d + 2. Finally we present an optimal broadcast scheme for these bipartite double loop graphs