# Cycle and Path Embedding on 5-ary N-cubes

Tsong-Jie Lin; Sun-Yuan Hsieh; Hui-Ling Huang

RAIRO - Theoretical Informatics and Applications (2008)

- 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 43.1 (2008): 133-144. <http://eudml.org/doc/92902>.

@article{Lin2008,

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.
},

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

journal = {RAIRO - Theoretical Informatics and Applications},

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

language = {eng},

month = {2},

number = {1},

pages = {133-144},

publisher = {EDP Sciences},

title = {Cycle and Path Embedding on 5-ary N-cubes},

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

volume = {43},

year = {2008},

}

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

DA - 2008/2//

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

LA - eng

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

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

ER -

## References

top- 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.
- 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.68510
- J. Chang, J. Yang and Y. Chang, Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs. Networks44 (2004) 302–310. Zbl1055.05076
- 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.
- S.Y. Hsieh, T.J. Lin and H.-L. Huang, Panconnectivity and edge-pancyclicity of 3-ary N-cubes. J. Supercomputing42 (2007) 225–233.
- F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays . Trees . Hypercubes. Morgan Kaufmann, San Mateo, CA (1992). Zbl0743.68007
- M. Ma and J. M. Xu, Panconnectivity of locally twisted cubes. Appl. Math. Lett.19 (2006) 673–677. Zbl1118.05050
- B. Monien and H. Sudborough, Embedding one interconnection network in another. Computing Suppl.7 (1990) 257–282. Zbl0699.68017
- 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).
- Y. Sheng, F. Tian and B. Wei, Panconnectivity of locally connected claw-free graphs. Discrete Mathematics203 (1999) 253–260. Zbl0934.05078
- Z.M. Song and Y.S. Qin, A new sufficient condition for panconnected graphs. Ars Combinatoria34 (1992) 161–166. Zbl0770.05069
- 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.