×

Cycle and path embedding on 5-ary \(n\)-cubes. (English) Zbl 1156.68041

Summary: 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\geq 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\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[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.68510 · Zbl 1054.68510 · doi:10.1109/12.403718
[4] J. Chang, J. Yang and Y. Chang, Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs. Networks44 (2004) 302-310. · Zbl 1055.05076 · doi:10.1002/net.20039
[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. Supercomputing42 (2007) 225-233.
[8] F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays . Trees . Hypercubes. Morgan Kaufmann, San Mateo, CA (1992). · Zbl 0743.68007
[9] M. Ma and J. M. Xu, Panconnectivity of locally twisted cubes. Appl. Math. Lett.19 (2006) 673-677. · Zbl 1118.05050 · doi:10.1016/j.aml.2005.08.021
[10] B. Monien and H. Sudborough, Embedding one interconnection network in another. Computing Suppl.7 (1990) 257-282. · Zbl 0699.68017
[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). · Zbl 0761.70006
[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 Mathematics203 (1999) 253-260. · Zbl 0934.05078 · doi:10.1016/S0012-365X(99)00010-2
[15] Z.M. Song and Y.S. Qin, A new sufficient condition for panconnected graphs. Ars Combinatoria34 (1992) 161-166. · Zbl 0770.05069
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.