# Cycle and path embedding on 5-ary N-cubes

Tsong-Jie Lin; Sun-Yuan Hsieh; Hui-Ling Huang^{[1]}

- [1] Department of Information Management, Southern Taiwan University, No. 1, NanTai Street, Tainan 71005, Taiwan;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

- Volume: 43, Issue: 1, page 133-144
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLin, Tsong-Jie, Hsieh, Sun-Yuan, and Huang, Hui-Ling. "Cycle and path embedding on 5-ary N-cubes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.1 (2009): 133-144. <http://eudml.org/doc/245576>.

@article{Lin2009,

abstract = {We study two topological properties of the 5-ary $n$-cube $Q_\{n\}^\{5\}$. Given two arbitrary distinct nodes $x$ and $y$ in $Q_\{n\}^\{5\}$, we prove that there exists an $x$-$y$ path of every length ranging from $2n$ to $5^\{n\}-1$, where $n\ge 2$. Based on this result, we prove that $Q_\{n\}^\{5\}$ is 5-edge-pancyclic by showing that every edge in $Q_\{n\}^\{5\}$ lies on a cycle of every length ranging from $5$ to $5^\{n\}$.},

affiliation = {Department of Information Management, Southern Taiwan University, No. 1, NanTai Street, Tainan 71005, Taiwan;},

author = {Lin, Tsong-Jie, Hsieh, Sun-Yuan, Huang, Hui-Ling},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {graph-theoretic interconnection networks; hypercubes; $k$-ary $n$-cubes; panconnectivity; edge-pancyclicity; -ary -cubes},

language = {eng},

number = {1},

pages = {133-144},

publisher = {EDP-Sciences},

title = {Cycle and path embedding on 5-ary N-cubes},

url = {http://eudml.org/doc/245576},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Lin, Tsong-Jie

AU - Hsieh, Sun-Yuan

AU - Huang, Hui-Ling

TI - Cycle and path embedding on 5-ary N-cubes

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2009

PB - EDP-Sciences

VL - 43

IS - 1

SP - 133

EP - 144

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

LA - eng

KW - graph-theoretic interconnection networks; hypercubes; $k$-ary $n$-cubes; panconnectivity; edge-pancyclicity; -ary -cubes

UR - http://eudml.org/doc/245576

ER -

## References

top- [1] S.G. Akl, Parallel Computation: Models and Methods Prentice Hall, NJ (1997).
- [2] S. Borkar, R. Cohn, G. Cox, S. Gleason, T. Gross, H.T. Kung, M. Lam, B. Moore, C. Peterson, J. Pieper, L. Rankin, P.S. Tseng, J. Sutton, J. Urbanski and J. Webb, iWarp: an integrated solution to high-speed parallel computing, Proceedings of the 1988 ACM/IEEE conference on Supercomputing (1988) 330–339.
- [3] B. Bose, B. Broeg, Y.G. Kwon and Y. Ashir, Lee distance and topological properties of k-ary n-cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. Zbl1054.68510MR1349941
- [4] J. Chang, J. Yang and Y. Chang, Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs. Networks 44 (2004) 302–310. Zbl1055.05076MR2098393
- [5] K. Day and A.E. Al-Ayyoub, Fault diameter of k-ary n-cube Networks. IEEE Transactions on Parallel and Distributed Systems, 8 (1997) 903–907.
- [6] S.A. Ghozati and H.C. Wasserman, The $k$-ary $n$-cube network: modeling, topological properties and routing strategies. Comput. Electr. Eng. (2003) 1271–1284.
- [7] S.Y. Hsieh, T.J. Lin and H.-L. Huang, Panconnectivity and edge-pancyclicity of 3-ary N-cubes. J. Supercomputing 42 (2007) 225–233.
- [8] F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays $\xb7$ Trees $\xb7$ Hypercubes. Morgan Kaufmann, San Mateo, CA (1992). Zbl0743.68007MR1137272
- [9] M. Ma and J. M. Xu, Panconnectivity of locally twisted cubes. Appl. Math. Lett. 19 (2006) 673–677. Zbl1118.05050MR2224423
- [10] B. Monien and H. Sudborough, Embedding one interconnection network in another. Computing Suppl. 7 (1990) 257–282. Zbl0699.68017MR1059934
- [11] W. Oed, Massively parallel processor system CRAY T3D. Technical Report, Cray Research GmbH (1993).
- [12] A.L. Rosenberg, Cycles in Networks. Technical Report: UM-CS-1991-020, University of Massachusetts, Amherst, MA, USA (1991).
- [13] C.L. Seitz et al., Submicron systems architecture project semi-annual technical report. Technical Report Caltec-CS-TR-88-18, California Institute of Technology (1988).
- [14] Y. Sheng, F. Tian and B. Wei, Panconnectivity of locally connected claw-free graphs. Discrete Mathematics 203 (1999) 253–260. Zbl0934.05078MR1696247
- [15] Z.M. Song and Y.S. Qin, A new sufficient condition for panconnected graphs. Ars Combinatoria 34 (1992) 161–166. Zbl0770.05069MR1206559
- [16] D. Wang, T. An, M. Pan, K. Wang and S. Qu, Hamiltonian-like properies of $k$-Ary $n$-Cubes, in Proceedings PDCAT05 of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05), IEEE Computer Society Press (2005) pp. 1002–1007.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.