A Recurrence for the Surface Area of the ($n, k$)-Star Graph

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.