The Twisted N-Cube with Application to Multiprocessing

Abdol Hossein Esfahanian; Lionel M. Ni

doi:10.1109/12.67323

The Twisted N-Cube with Application to Multiprocessing

Abdol Hossein Esfahanian, Lionel M. Ni

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

126 Citations (Scopus)

Abstract

We show that by exchanging any two independent edges in any shortest cycle of the n-cube (n>3), its diameter decreases by one unit. This leads us to define a new class of n-regular graphs, denoted TQn, with 2n vertices and diameter n — 1, which has the (n — l)-cube as subgraph. Other properties of TQnsuch as connectivity and the lengths of the disjoints paths are also investigated. Moreover, we show that the complete binary tree on 2n — 1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQn. Finally, we discuss how these results can be used to enhance existing hypercube multiprocessors.

Original language	English
Pages (from-to)	88-93
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	40
Issue number	1
DOIs	https://doi.org/10.1109/12.67323
Publication status	Published - Jan 1991
Externally published	Yes

Keywords

Binary tree
N-cube
graph theory
hypercube multiprocessors
message routing
pattern embedding

Access to Document

10.1109/12.67323

Cite this

@article{4f4e6947fa0f4279ba9b8ccc7823d9fe,

title = "The Twisted N-Cube with Application to Multiprocessing",

abstract = "We show that by exchanging any two independent edges in any shortest cycle of the n-cube (n>3), its diameter decreases by one unit. This leads us to define a new class of n-regular graphs, denoted TQn, with 2n vertices and diameter n — 1, which has the (n — l)-cube as subgraph. Other properties of TQnsuch as connectivity and the lengths of the disjoints paths are also investigated. Moreover, we show that the complete binary tree on 2n — 1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQn. Finally, we discuss how these results can be used to enhance existing hypercube multiprocessors.",

keywords = "Binary tree, N-cube, graph theory, hypercube multiprocessors, message routing, pattern embedding",

author = "Esfahanian, \{Abdol Hossein\} and Ni, \{Lionel M.\}",

year = "1991",

month = jan,

doi = "10.1109/12.67323",

language = "English",

volume = "40",

pages = "88--93",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - The Twisted N-Cube with Application to Multiprocessing

AU - Esfahanian, Abdol Hossein

AU - Ni, Lionel M.

PY - 1991/1

Y1 - 1991/1

N2 - We show that by exchanging any two independent edges in any shortest cycle of the n-cube (n>3), its diameter decreases by one unit. This leads us to define a new class of n-regular graphs, denoted TQn, with 2n vertices and diameter n — 1, which has the (n — l)-cube as subgraph. Other properties of TQnsuch as connectivity and the lengths of the disjoints paths are also investigated. Moreover, we show that the complete binary tree on 2n — 1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQn. Finally, we discuss how these results can be used to enhance existing hypercube multiprocessors.

AB - We show that by exchanging any two independent edges in any shortest cycle of the n-cube (n>3), its diameter decreases by one unit. This leads us to define a new class of n-regular graphs, denoted TQn, with 2n vertices and diameter n — 1, which has the (n — l)-cube as subgraph. Other properties of TQnsuch as connectivity and the lengths of the disjoints paths are also investigated. Moreover, we show that the complete binary tree on 2n — 1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQn. Finally, we discuss how these results can be used to enhance existing hypercube multiprocessors.

KW - Binary tree

KW - N-cube

KW - graph theory

KW - hypercube multiprocessors

KW - message routing

KW - pattern embedding

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:A1991EW99500009

UR - https://openalex.org/W2101070933

U2 - 10.1109/12.67323

DO - 10.1109/12.67323

M3 - Journal Article

SN - 0018-9340

VL - 40

SP - 88

EP - 93

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 1

ER -

The Twisted N-Cube with Application to Multiprocessing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this