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

Abstract

top
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 2 n to 5 n - 1 , where n ≥ 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 .

How to cite

top

Lin, 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. [1] S.G. Akl, Parallel Computation: Models and Methods Prentice Hall, NJ (1997). 
  2. [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. [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. [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. [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. [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. [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. [8] F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays · Trees · Hypercubes. Morgan Kaufmann, San Mateo, CA (1992). Zbl0743.68007MR1137272
  9. [9] M. Ma and J. M. Xu, Panconnectivity of locally twisted cubes. Appl. Math. Lett. 19 (2006) 673–677. Zbl1118.05050MR2224423
  10. [10] B. Monien and H. Sudborough, Embedding one interconnection network in another. Computing Suppl. 7 (1990) 257–282. Zbl0699.68017MR1059934
  11. [11] W. Oed, Massively parallel processor system CRAY T3D. Technical Report, Cray Research GmbH (1993). 
  12. [12] A.L. Rosenberg, Cycles in Networks. Technical Report: UM-CS-1991-020, University of Massachusetts, Amherst, MA, USA (1991). 
  13. [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. [14] Y. Sheng, F. Tian and B. Wei, Panconnectivity of locally connected claw-free graphs. Discrete Mathematics 203 (1999) 253–260. Zbl0934.05078MR1696247
  15. [15] Z.M. Song and Y.S. Qin, A new sufficient condition for panconnected graphs. Ars Combinatoria 34 (1992) 161–166. Zbl0770.05069MR1206559
  16. [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 ?

top

You must be logged in to post comments.