AN ALGEBRAIC APPROACH FOR FINDING DISJOINT PATHS IN THE ALTERNATING GROUP GRAPH

摘要

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 the three disjoint paths in the graph AG_5. Their algorithm exploited the hierarchal 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.