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

Sun-Yuan Hsieh, Tsong Jie Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationThe 13th International Conference on Parallel and Distributed Systems, ICPADS
DOIs
Publication statusPublished - 2007 Dec 1
Event13th International Conference on Parallel and Distributed Systems, ICPADS - Hsinchu, Taiwan
Duration: 2007 Dec 52007 Dec 7

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume1
ISSN (Print)1521-9097

Other

Other13th International Conference on Parallel and Distributed Systems, ICPADS
CountryTaiwan
CityHsinchu
Period07-12-0507-12-07

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this