On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs

Abstract

We derive an explicit formula for the surface area of the arrangement graph, i.e. the number of vertices at a certain distance from the identity vertex in such a graph. We also present such formulas for the star graph, the alternating group graph, and the split-star graph, via their respective structural relationship to the arrangement graph.

Keywords:

• surface area
• explicit formula
• combinatorial analysis
• interconnection network
• arrangement graph
• Whitney numbers of the second kind

2010 AMS Subject Classifications:

• 05A10
• 05C12
• 20B25
• 65Y05
• 68M10
• 90B18

Acknowledgements

We are very grateful to two anonymous referees for helpful remarks and suggestions, which definitely led to an improvement of this paper.

Notes

For numerous examples of such simplification, readers are referred to [8, §5].