Hyper‐star graphs: Some topological properties and an optimal neighbourhood broadcasting algorithm
F. Zhang, K. Qiu, Jinsoo Kim · Concurrency and Computation Practice and Experience · 2015
Summary Hyper‐star graph HS(2n,n) was introduced to be a competitive model to both hypercubes and star graphs. In this paper, we study its properties by (1) giving a closed form solution to the surface area of HS(2n,n), (2) discussing its Hamiltonicity by establishing an isomorphism between the graph and the well‐known middle levels problem, and (3) showing that full binary trees can be embedded into HS(2n,n) with dilation 1. We also develop a single‐port optimal neighbourhood broadcasting algorithm for HS(2n,n). Copyright © 2015 John Wiley & Sons, Ltd.