Embedding of Cycles in Arrangement Graphs

Khaled Day; Anand Tripathi

doi:10.1109/12.238494

Embedding of Cycles in Arrangement Graphs

Khaled Day, Anand Tripathi

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

74 Scopus citations

Abstract

Arrangement graphs have been recently proposed as an attractive interconnection topology for large multiprocessor systems. In this correspondence, 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.

Original language	English (US)
Pages (from-to)	1002-1006
Number of pages	5
Journal	IEEE Transactions on Computers
Volume	42
Issue number	8
DOIs	https://doi.org/10.1109/12.238494
State	Published - Aug 1993

Keywords

Arrangement graphs
Hamiltonian cycles
disjoint cycles
embeddings
interconnection networks
star graphs

Publisher link

10.1109/12.238494

Find It

Find It at U of M Libraries

Cite this

@article{36c43a67866f4237969421efe59e1ebf,

title = "Embedding of Cycles in Arrangement Graphs",

abstract = "Arrangement graphs have been recently proposed as an attractive interconnection topology for large multiprocessor systems. In this correspondence, 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.",

keywords = "Arrangement graphs, Hamiltonian cycles, disjoint cycles, embeddings, interconnection networks, star graphs",

author = "Khaled Day and Anand Tripathi",

year = "1993",

month = aug,

doi = "10.1109/12.238494",

language = "English (US)",

volume = "42",

pages = "1002--1006",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "8",

}

TY - JOUR

T1 - Embedding of Cycles in Arrangement Graphs

AU - Day, Khaled

AU - Tripathi, Anand

PY - 1993/8

Y1 - 1993/8

N2 - Arrangement graphs have been recently proposed as an attractive interconnection topology for large multiprocessor systems. In this correspondence, 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.

AB - Arrangement graphs have been recently proposed as an attractive interconnection topology for large multiprocessor systems. In this correspondence, 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.

KW - Arrangement graphs

KW - Hamiltonian cycles

KW - disjoint cycles

KW - embeddings

KW - interconnection networks

KW - star graphs

UR - http://www.scopus.com/inward/record.url?scp=0027646440&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027646440&partnerID=8YFLogxK

U2 - 10.1109/12.238494

DO - 10.1109/12.238494

M3 - Article

AN - SCOPUS:0027646440

SN - 0018-9340

VL - 42

SP - 1002

EP - 1006

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 8

ER -

Embedding of Cycles in Arrangement Graphs

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this