A Recurrence for the Surface Area of the ($n, k$)-Star Graph
Ethan Gibbons, Ke Qiang Qiu · 2022
We present a simple recurrence for the surface area of the ($n, k$) -star graph,$0 < k < n$, i.e., the number of nodes at a certain distance from the identity node in the graph, an important parameter for interconnection networks in parallel computing. The family of the ($n, k$) -star graphs includes several popular interconnection networks such as the star graph and the alternating group network. Previously, a surface area recurrence has been obtained for a special case, e.g., when$k=n-1$, in the family of ($n, k$) -star. Our recurrence gives one single recurrence for all graphs in the family, thus completely solving the surface area of ($n, k$) -star for all$0 < k < n$. Compared to explicit surface area formulas previously obtained through complicated and involved combinatorial analysis and generating function approach, our derivation is more elementary and our recurrence gives a way to compute the surface area of the ($n, k$))-star efficiently.