Premium
Orienting split‐stars and alternating group graphs
Author(s) -
Cheng Eddie,
Lipman Marc J.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(200003)35:2<139::aid-net4>3.0.co;2-e
Subject(s) - combinatorics , stars , star (game theory) , computer science , mathematics , discrete mathematics , mathematical analysis , computer vision
Abstract Akers et al. proposed an interconnection topology, the star graph, as an alternative to the popular 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 ‐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. © 2000 John Wiley & Sons, Inc.