Design and analysis of the rotational binary graph as an alternative to hypercube and Torus

Network cost is equal to degree?×?diameter and is one of the important measurements when evaluating graphs. Torus and hypercube are very well-known graphs. When these graphs expand, a Torus has an advantage in that its degree does not increase. A hypercube has a shorter diameter than that of other graphs, because when the graph expands, the diameter increases by 1. Hypercube Q_n has 2ⁿ nodes, and its diameter is n. We propose the rotational binary graph (RBG), which has the advantages of both hypercube and Torus. RBG_n has 2ⁿ nodes and a degree of 4. The diameter of RBG_n would be 1.5n?+?1. In this paper, we first examine the topology properties of RBG. Second, we construct a binary spanning tree in RBG. Third, we compare other graphs to RBG considering network cost specifically. Fourth, we suggest a broadcast algorithm with a time complexity of 2n???2. Finally, we prove that RBG_n embedded into hypercube Q_n results in dilation n, and expansion 1, and congestion 7.