Embedding cycles and paths in a k-ary n-cube

Sun-Yuan Hsieh; Tsong Jie Lin

doi:10.1109/ICPADS.2007.4447775

Embedding cycles and paths in a k-ary n-cube

Sun-Yuan Hsieh
, Tsong Jie Lin

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

17 Citations (Scopus)

Abstract

The k-ary n-cube, denoted by Q_n^k, has been one of the most common interconnection networks. In this paper, we study some topological properties of Q_n^k. Given two arbitrary distinct nodes x and y in Q_n^k, we show that there exists an x-y path of every length from [k/2] n to kⁿ - 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Q_n^k lies on a cycle of every length from k to kⁿ. In addition, we show that Q_n^k is both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.

Original language	English
Title of host publication	The 13th International Conference on Parallel and Distributed Systems, ICPADS
DOIs	https://doi.org/10.1109/ICPADS.2007.4447775
Publication status	Published - 2007 Dec 1
Event	13th International Conference on Parallel and Distributed Systems, ICPADS - Hsinchu, Taiwan Duration: 2007 Dec 5 → 2007 Dec 7

Publication series

Name	Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume	1
ISSN (Print)	1521-9097

Other

Other	13th International Conference on Parallel and Distributed Systems, ICPADS
Country/Territory	Taiwan
City	Hsinchu
Period	07-12-05 → 07-12-07

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/ICPADS.2007.4447775

Cite this

@inproceedings{4f7d13d40db2446bbde026af2d68f32c,

title = "Embedding cycles and paths in a k-ary n-cube",

abstract = "The k-ary n-cube, denoted by Qnk, has been one of the most common interconnection networks. In this paper, we study some topological properties of Qnk. Given two arbitrary distinct nodes x and y in Qnk, we show that there exists an x-y path of every length from [k/2] n to kn - 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Qnk lies on a cycle of every length from k to kn. In addition, we show that Qnk is both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.",

author = "Sun-Yuan Hsieh and Lin, \{Tsong Jie\}",

year = "2007",

month = dec,

day = "1",

doi = "10.1109/ICPADS.2007.4447775",

language = "English",

isbn = "9781424418909",

series = "Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS",

booktitle = "The 13th International Conference on Parallel and Distributed Systems, ICPADS",

note = "13th International Conference on Parallel and Distributed Systems, ICPADS ; Conference date: 05-12-2007 Through 07-12-2007",

}

Hsieh, S-Y & Lin, TJ 2007, Embedding cycles and paths in a k-ary n-cube. in The 13th International Conference on Parallel and Distributed Systems, ICPADS., 4447775, Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS, vol. 1, 13th International Conference on Parallel and Distributed Systems, ICPADS, Hsinchu, Taiwan, 07-12-05. https://doi.org/10.1109/ICPADS.2007.4447775

TY - GEN

T1 - Embedding cycles and paths in a k-ary n-cube

AU - Hsieh, Sun-Yuan

AU - Lin, Tsong Jie

PY - 2007/12/1

Y1 - 2007/12/1

N2 - The k-ary n-cube, denoted by Qnk, has been one of the most common interconnection networks. In this paper, we study some topological properties of Qnk. Given two arbitrary distinct nodes x and y in Qnk, we show that there exists an x-y path of every length from [k/2] n to kn - 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Qnk lies on a cycle of every length from k to kn. In addition, we show that Qnk is both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.

AB - The k-ary n-cube, denoted by Qnk, has been one of the most common interconnection networks. In this paper, we study some topological properties of Qnk. Given two arbitrary distinct nodes x and y in Qnk, we show that there exists an x-y path of every length from [k/2] n to kn - 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Qnk lies on a cycle of every length from k to kn. In addition, we show that Qnk is both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.

UR - https://www.scopus.com/pages/publications/48049123691

UR - https://www.scopus.com/pages/publications/48049123691#tab=citedBy

U2 - 10.1109/ICPADS.2007.4447775

DO - 10.1109/ICPADS.2007.4447775

M3 - Conference contribution

AN - SCOPUS:48049123691

SN - 9781424418909

T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS

BT - The 13th International Conference on Parallel and Distributed Systems, ICPADS

T2 - 13th International Conference on Parallel and Distributed Systems, ICPADS

Y2 - 5 December 2007 through 7 December 2007

ER -

Embedding cycles and paths in a k-ary n-cube

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this