Unidirectional (n, k)-Star Graphs.

Arrangement graphs and (n,k)-star graphs were introduced as generalizations of star graphs. They were introduced to provide a wider set of choices for the order of topologically attractive interconnection networks. Unidirectional interconnection networks are more appropriate in many applications. Cheng and Lipman, and Day and Tripathi studied the unidirectional star graphs, and Cheng and Lipman studied orientation of arrangement graphs. In this paper, we show that every (n,k)-star graph can be oriented to a maximally are-connected graph when the regularity of the graph is even. If the regularity is odd, then the resulting directed graph can be augmented to a maximally arc-connected directed graph by adding a directed matching. In either case, the diameter of the resulting directed graph is small. Moreover, there exists a simple and near-optimal routing algorithm. [ABSTRACT FROM AUTHOR]