A GENERATING FUNCTION APPROACH TO THE SURFACE AREAS OF SOME INTERCONNECTION NETWORKS
Eddie Cheng, Ke Qiang Qiu, Zhizhang Shen · Journal of Interconnection Networks · 2009
An important and interesting parameter of an interconnection network is the number of vertices of a specific distance from a specific vertex. This is known as the surface area or the Whitney number of the second kind. In this paper, we give explicit formulas for the surface areas of the (n, k)-star graphs and the arrangement graphs via the generating function technique. As a direct consequence, these formulas will also provide such explicit formulas for the star graphs, the alternating group graphs and the split-stars since these graphs are related to the (n, k)-star graphs and the arrangement graphs. In addition, we derive the average distances for these graphs.