EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS

Authors
DAY K TRIPATHI A
Citation
K. Day et A. Tripathi, EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS, I.E.E.E. transactions on computers, 42(8), 1993, pp. 1002-1006
Citations number
7
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Applications & Cybernetics
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
42
Issue
8
Year of publication
1993
Pages
1002 - 1006
Database
ISI
SICI code
0018-9340(1993)42:8<1002:EOCIAG>2.0.ZU;2-Z
Abstract
Arrangement graphs have been recently proposed as an attractive interc onnection topology for large multiprocessor systems. In this correspon dence, we further study these graphs by first proving the existence of Hamiltonian cycles in any arrangement graph. Secondly, we prove that an arrangement graph contains cycles of all lengths ranging between 3 and the size of the graph. Finally, we show that an arrangement graph can be decomposed into node disjoint cycles in many different ways.