Topological Properties of Bi-rotator Graphs

H.-R. Lin and C.-C. Hsu (PRC)

Keywords

birotator graph, rotator graph, routing,Hamiltonian, dilation, embedding

Abstract

This paper presents a new interconnection network called bi-rotator graph. It is well known that the rotator graph is a directed graph. The bi-rotator graph is constructed by making edges of the rotator graph bidirectional. The bidirectional edges can help to reduce the average routing distance and increase the flexibility of applied applications. Therefore, we propose the new interconnection scheme here as an alternative to the rotator graph. In this paper, we will first illustrate how to construct the bi-rotator graph, presenting the node-to-node routing algorithm. Next, we will present the algorithm for building Hamiltonian cycle, demonstrating that the bi-rotator graph is Hamiltonian. Finally, we provide a dilation-one algorithm for embedding arbitrary size of cycle into a bi-rotator graph.

Important Links:



Go Back