Orienting split-stars and alternating group graphs

✍ Scribed by Cheng, Eddie; Lipman, Marc J.

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 148 KB
• Volume: 35
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(200003)35:2<139::aid-net4>3.0.co;2-e

✦ Synopsis

Akers et al. proposed an interconnection topology, the star graph, as an alternative to the popular n n n-cube. Cheng et al. proposed the split-star as an alternative to the star graph and a companion graph to the alternating group graph proposed by Jwo et al. Star graphs, alternating group graphs, and split-stars are advantageous over n n n-cubes in many aspects. Day and Tripathi proposed an assignment of directions to the edges of the star graph and showed that the resulting directed graph is strongly connected and has a simple routing algorithm. In this paper, we give simple routing algorithms for a proposed orientation of alternating group graphs and split-stars. The resulting directed graphs are not only strongly connected but they have maximal arc-fault tolerance and a small diameter.