Unidirectional star graphs

We propose an assignment of directions to the edges of the n-star graph and derive attractive properties for the resulting unidirectional star graph US_n. A simple polarity function is used to define the directions of the edges. US_n is shown to be strongly connected and recursively structured. The number of incoming ports of a node in US_n is equal to the number of its outgoing ports (plus or minus one when n is even). The polarities of the ports of a neighboring node can be directly obtained from the polarities of the ports of the local node. These properties have allowed the design of a near optimal distributed routing algorithm as indicated by simulation results on all US_n graphs with up to 362,880 nodes.