A Generating Function Approach to the Edge Surface Area of the Arrangement Graphs

摘要

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. It turns out that, in some applications, the number of vertices of a specific distance from a subgraph H is also important. A fundamental starting point is to consider the number of vertices of a specific distance from an edge, which is called the edge surface area. In this paper, we give an explicit formula for the edge surface area of arrangement graphs via the generating function technique. As a direct consequence, it will also provide such explicit formulas for star graphs, alternating group graphs and split stars.