An Algebraic Approach for Finding Disjoint Paths in the Alternating Group Graph

Abstract

For the purpose of large scale computing, we are interested in linking computers into large interconnection networks. In order for these networks to be useful, the underlying graph must possess desirable properties such as a large number of vertices, high connectivity, and small diameter. In this paper, we are interested in the alternating group graph, as an interconnection network, and the \( k \)-Disjoint Path Problem. In 2005, Cheng, Kikas, and Kruk showed that the alternating group graph, \( AG_n \), has the \( (n – 2) \)-Disjoint Path Property. However, their proof was an existence proof only; they did not show how to actually construct the \( (n – 2) \) disjoint paths. In 2006, Boats, Kikas, and Oleksik developed an algorithm for constructing three disjoint paths in the graph \( AG_5 \). Their algorithm exploited the hierarchical structure of \( AG_n \) to construct the paths. In this paper, we develop a purely algebraic algorithm that constructs the \( (n – 2) \) disjoint paths from scratch. This algebraic approach can be used for other Cayley graphs such as the split-star and the star graphs. Indeed, we believe that our approach can be used for any Cayley graph. We close with remarks on possible research directions stemming from this work.