RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2008004

Cycle and Path Embedding on 5-ary N-cubes

Tsong-Jie Lin¹, Sun-Yuan Hsieh¹ and Hui-Ling Huang<sup>2

1</sup>  Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan; tsong0215@yahoo.com.tw
²  Department of Information Management, Southern Taiwan University, No. 1, NanTai Street, Tainan 71005, Taiwan; hlhuang@mail.stut.edu.tw

(Received May 3, 2007. Accepted January 22, 2008. Published online 28 February 2008.)

Abstract
We study two topological properties of the 5-ary n-cube Q_n⁵. Given two arbitrary distinct nodes x and y in Q_n⁵, we prove that there exists an x-y path of every length ranging from 2n to 5ⁿ-1, where . Based on this result, we prove that Q_n⁵ is 5-edge-pancyclic by showing that every edge in Q_n⁵ lies on a cycle of every length ranging from 5 to 5ⁿ.

Mathematics Subject Classification. 68R10, 68R05, 05C12

Key words: Graph-theoretic interconnection networks -- hypercubes -- k-ary n-cubes -- panconnectivity -- edge-pancyclicity


© EDP Sciences 2008