Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-29T05:49:15.083Z Has data issue: false hasContentIssue false
  • English
  • Français

Cycle and Path Embedding on 5-ary N-cubes

Published online by Cambridge University Press:  28 February 2008

Tsong-Jie Lin ,
Sun-Yuan Hsieh  and
Hui-Ling Huang
Tsong-Jie Lin
Affiliation:
Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan; [email protected] [email protected]
Sun-Yuan Hsieh
Affiliation:
Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan; [email protected] [email protected]
Hui-Ling Huang
Affiliation:
Department of Information Management, Southern Taiwan University, No. 1, NanTai Street, Tainan 71005, Taiwan; [email protected]
Get access

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 5n - 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 5n.

Keywords

Graph-theoretic interconnection networkshypercubesk-ary n-cubespanconnectivityedge-pancyclicity.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 1 , January 2009 , pp. 133 - 144
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

S.G. Akl, Parallel Computation: Models and Methods Prentice Hall, NJ (1997).
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.
Bose, B., Broeg, B., Kwon, Y.G. and Ashir, Y., Lee distance and topological properties of k-ary n-cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. CrossRef
Chang, J., Yang, J. and Chang, Y., Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs. Networks 44 (2004) 302–310. CrossRefPubMed
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.
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.
Hsieh, S.Y., Lin, T.J. and Huang, H.-L., Panconnectivity and edge-pancyclicity of 3-ary N-cubes. J. Supercomputing 42 (2007) 225–233. CrossRef
F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays . Trees . Hypercubes. Morgan Kaufmann, San Mateo, CA (1992).
Ma, M. and Panconnectivity, J. M. Xu of locally twisted cubes. Appl. Math. Lett. 19 (2006) 673–677. CrossRef
Monien, B. and Sudborough, H., Embedding one interconnection network in another. Computing Suppl. 7 (1990) 257–282. CrossRef
W. Oed, Massively parallel processor system CRAY T3D. Technical Report, Cray Research GmbH (1993).
A.L. Rosenberg, Cycles in Networks. Technical Report: UM-CS-1991-020, University of Massachusetts, Amherst, MA, USA (1991).
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).
Sheng, Y., Tian, F. and Wei, B., Panconnectivity of locally connected claw-free graphs. Discrete Mathematics 203 (1999) 253–260. CrossRef
Song, Z.M. and Qin, Y.S., A new sufficient condition for panconnected graphs. Ars Combinatoria 34 (1992) 161–166.
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.