Portal de Periódicos da CAPES

UNIDIRECTIONAL (n, k)-STAR GRAPHS

2002; World Scientific; Volume: 03; Issue: 01n02 Linguagem: Inglês

10.1142/s0219265902000525

1793-6713

Eddie Cheng, Marc J. Lipman,

Graphene and Nanomaterials Applications

Arrangement graphs 14 and (n, k)-star graphs 11 were introduced as generalizations of star graphs 1 . 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 5 , and Day and Tripathi 17 studied the unidirectional star graphs, and Cheng and Lipman 7 studied orientation of arrangement graphs. In this paper, we show that every (n, k)-star graph can be oriented to a maximally arc-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.