Topological Properties of Bi-Rotator Graphs

Hon-Ren LIN; Chiun-Chieh HSU

Topological Properties of Bi-Rotator Graphs

Hon-Ren LIN, Chiun-Chieh HSU

Full Text Views

0

Share
Cite this

Summary :

This paper presents a new interconnection network called bi-rotator graph. It is originated from the rotator graph. The rotator graph has many unidirectional edges and 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 applications. Therefore, we propose the bi-rotator graph as an alternative to the rotator graph. In this paper, we will first illustrate how to construct the bi-rotator graph and present the node-to-node routing algorithm. Next, we will propose the algorithm for building Hamiltonian cycle, which demonstrates that the bi-rotator graph is Hamiltonian. Finally, we provide a dilation-one algorithm for embedding arbitrary size of cycle into the bi-rotator graph and show that the bi-rotator graph is Hamiltonian-connected.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.10 pp.2172-2178

Publication Date: 2003/10/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Theory/Models of Computation

Cite this

Copy

Hon-Ren LIN, Chiun-Chieh HSU, "Topological Properties of Bi-Rotator Graphs" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 10, pp. 2172-2178, October 2003, doi: .
Abstract: This paper presents a new interconnection network called bi-rotator graph. It is originated from the rotator graph. The rotator graph has many unidirectional edges and 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 applications. Therefore, we propose the bi-rotator graph as an alternative to the rotator graph. In this paper, we will first illustrate how to construct the bi-rotator graph and present the node-to-node routing algorithm. Next, we will propose the algorithm for building Hamiltonian cycle, which demonstrates that the bi-rotator graph is Hamiltonian. Finally, we provide a dilation-one algorithm for embedding arbitrary size of cycle into the bi-rotator graph and show that the bi-rotator graph is Hamiltonian-connected.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e86-d_10_2172/_p

Copy

@ARTICLE{e86-d_10_2172,
author={Hon-Ren LIN, Chiun-Chieh HSU, },
journal={IEICE TRANSACTIONS on Information},
title={Topological Properties of Bi-Rotator Graphs},
year={2003},
volume={E86-D},
number={10},
pages={2172-2178},
abstract={This paper presents a new interconnection network called bi-rotator graph. It is originated from the rotator graph. The rotator graph has many unidirectional edges and 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 applications. Therefore, we propose the bi-rotator graph as an alternative to the rotator graph. In this paper, we will first illustrate how to construct the bi-rotator graph and present the node-to-node routing algorithm. Next, we will propose the algorithm for building Hamiltonian cycle, which demonstrates that the bi-rotator graph is Hamiltonian. Finally, we provide a dilation-one algorithm for embedding arbitrary size of cycle into the bi-rotator graph and show that the bi-rotator graph is Hamiltonian-connected.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Topological Properties of Bi-Rotator Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2172
EP - 2178
AU - Hon-Ren LIN
AU - Chiun-Chieh HSU
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2003
AB - This paper presents a new interconnection network called bi-rotator graph. It is originated from the rotator graph. The rotator graph has many unidirectional edges and 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 applications. Therefore, we propose the bi-rotator graph as an alternative to the rotator graph. In this paper, we will first illustrate how to construct the bi-rotator graph and present the node-to-node routing algorithm. Next, we will propose the algorithm for building Hamiltonian cycle, which demonstrates that the bi-rotator graph is Hamiltonian. Finally, we provide a dilation-one algorithm for embedding arbitrary size of cycle into the bi-rotator graph and show that the bi-rotator graph is Hamiltonian-connected.
ER -