Length two path-centred surface areas for the arrangement graph

Abstract

We suggest the notion of H-centred surface area of a graph G, where H is a subgraph of G, i.e. the number of vertices in G at a certain distance from H, and focus on the special case when H is a length two path to derive an explicit formula for the length two path-centred surface areas of the general and scalable arrangement graph.

Keywords:

• length two path-centred surface areas
• arrangement graph
• combinatorial analysis
• interconnection network
• parallel computing

2010 AMS Subject Classifications:

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

Acknowledgements

We greatly appreciate the thorough review and insightful comments made by two anonymous referees, which led to a clarification and further improvement of this paper.

Notes

1. A cycle is trivial if it contains exactly one symbol, called a fixed point. It is non-trivial otherwise.

2. When 1 occurs in an external cycle, we need to consider an additional symbol, i.e. the external symbol associated with the external cycle where 1 occurs.

3. We notice that , which swaps two internal symbols with one external symbol in A_{n, k}, k∈[2, n−1], is the only viable length two path allowed for A_{n, n−1} ≡ S_n.