×

Hamiltonian cycles passing through linear forests in \(k\)-ary \(n\)-cubes. (English) Zbl 1231.05162

Summary: The \(k\)-ary \(n\)-cube is one of the most popular interconnection networks for parallel and distributed systems. A linear forest in a graph is a subgraph, each component of which is a path. In this paper, we investigate the existence of Hamiltonian cycles passing through linear forests in the \(k\)-ary \(n\)-cube. For any \(n\geq 2\) and \(k\geq 3\), we show that the \(k\)-ary \(n\)-cube admits a Hamiltonian cycle passing through a linear forest with at most \(2n - 1\) edges.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C05 Trees
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adiga, N. R.; Blumrich, M. A.; Chen, D.; Coteus, P.; Gara, A.; Giampapa, M. E.; Heidelberger, P.; Singh, S.; Steinmacher-Burow, B. D.; Takken, T.; Tsao, M.; Vranas, P., Blue Gene/L torus interconnection network, IBM Journal of Research and Development, 49, 2, 265-276 (2005)
[2] Ahuja, Sandeep K.; Ramasubramanian, Srinivasan, All-to-all disjoint multipath routing using cycle embedding, Computer Networks, 52, 7, 1506-1517 (2008)
[3] Ed Anderson, Jeff Brooks, Charles Grassl, Steve Scott, Performance of the Cray T3E multiprocessor, in: Proceedings of Supercomputing, ACM/IEEE 1997 Conference, November 1997, pp. 1-17.; Ed Anderson, Jeff Brooks, Charles Grassl, Steve Scott, Performance of the Cray T3E multiprocessor, in: Proceedings of Supercomputing, ACM/IEEE 1997 Conference, November 1997, pp. 1-17.
[4] Ashir, Yaagoub A.; Stewart, Iain A., Fault-tolerant embeddings of Hamiltonian circuits in \(k\)-ary \(n\)-cubes, SIAM Journal on Discrete Mathematics, 15, 3, 317-328 (2002) · Zbl 1018.68058
[5] Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer-Verlag: Springer-Verlag New York · Zbl 1134.05001
[6] Bose, Bella; Broeg, Bob; Kwon, Younggeun; Ashir, Yaagoub, Lee distance and topological propertices of \(k\)-ary \(n\)-cubes, IEEE Transactions on Computers, 44, 8, 1021-1030 (1995) · Zbl 1054.68510
[7] Caha, Rostislav; Koubek, V., Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, Journal of Graph Theory, 51, 2, 137-169 (2006) · Zbl 1084.05041
[8] Chan, Mee Yee; Lee, Shiang-Jen, On the existence of Hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics, 4, 4, 511-527 (1991) · Zbl 0747.05035
[9] Chen, Xie-Bin, Cycles passing through prescribed edges in a hypercube with some faulty edges, Information Processing Letters, 104, 6, 211-215 (2007) · Zbl 1184.68113
[10] Dally, William J., Performance analysis of \(k\)-ary \(n\)-cube interconnection networks, IEEE Transactions on Computers, 39, 6, 775-785 (1990)
[11] Dong, Qiang; Yang, Xiaofan; Wang, Dajin, Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links, Information Sciences, 180, 1, 198-208 (2010) · Zbl 1183.68089
[12] Dvořák, Tomáš, Hamiltonian cycles with prescribed edges in hypercubes, SIAM Journal on Discrete Mathematics, 19, 1, 135-144 (2005) · Zbl 1082.05056
[13] Dvořák, Tomáš; Gregor, Petr, Hamiltonian paths with prescribed edges in hypercubes, Discrete Mathematics, 307, 16, 1982-1998 (2007) · Zbl 1119.05060
[14] Ghozati, S. A.; Wasserman, H. C., The \(k\)-ary \(n\)-cube network: modeling, topological properties and routing strategies, Computers & Electrical Engineering, 25, 3, 155-168 (1999)
[15] Sun-Yuan Hsieh, Tsong-Jie Lin, Embedding cycles and paths in a \(kn\); Sun-Yuan Hsieh, Tsong-Jie Lin, Embedding cycles and paths in a \(kn\)
[16] Hsieh, Sun-Yuan; Lin, Tsong-Jie; Huang, Hui-Ling, Panconnectivity and edge-pancyclicity of 3-ary \(n\)-cubes, Journal of Supercomputing, 42, 2, 225-233 (2007)
[17] Hsieh, Sun-Yuan; Lin, Tsong-Jie; Huang, Hui-Ling, Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes, Networks, 54, 1, 1-11 (2009) · Zbl 1205.05126
[18] Huang, Chien-Hung, Strongly Hamiltonian laceability of the even \(k\)-ary \(n\)-cube, Computers & Electrical Engineering, 35, 5, 659-663 (2009) · Zbl 1187.68109
[19] R.E. Kessler, J.L. Schwarzmeier, Cray T3D: a new dimension for Cray research, in: Proceedings of the 38th IEEE Computer Society International Conference, San Francisco, CA, 1993, pp. 176-182.; R.E. Kessler, J.L. Schwarzmeier, Cray T3D: a new dimension for Cray research, in: Proceedings of the 38th IEEE Computer Society International Conference, San Francisco, CA, 1993, pp. 176-182.
[20] Lin, Tsong-Jie; Hsieh, Sun-Yuan; Huang, Hui-Ling, Cycle and path embedding on 5-ary \(n\)-cubes, Theoretical Informatics and Applications, 43, 1, 133-144 (2009) · Zbl 1156.68041
[21] Lin, Shangwei; Wang, Shiying; Li, Chunfang, Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes with faulty elements, Discrete Applied Mathematics, 159, 4, 212-223 (2011) · Zbl 1214.68087
[22] Mao, Weizhen; Nicol, David M., On \(k\)-ary \(n\)-cubes: theory and applications, Discrete Applied Mathematics, 129, 1, 171-193 (2003) · Zbl 1048.68063
[23] Peterson, Craig; Sutton, James; Wiley, Paul, iWarp: a 100-MOPS, LIW microprocessor for multicomputers, IEEE Micro, 11, 3, 26-29 (1991), 81-87
[24] Stewart, Iain A.; Xiang, Yonghong, Bipanconnectivity and bipancyclicity in \(k\)-ary \(n\)-cubes, IEEE Transactions on Parallel and Distributed Systems, 20, 1, 25-33 (2009)
[25] Tsai, Chang-Hsiung, Fault-free cycles passing through prescribed paths in hypercubes with faulty edges, Applied Mathematics Letters, 22, 6, 852-855 (2009) · Zbl 1200.05242
[26] Wang, Wen-Qing; Chen, Xie-Bin, A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges, Information Processing Letters, 107, 6, 205-210 (2008) · Zbl 1186.68035
[27] Wang, Shiying; Lin, Shangwei, Path embeddings in faulty 3-ary \(n\)-cubes, Information Sciences, 180, 1, 191-197 (2010) · Zbl 1183.68093
[28] Yang, Ming-Chien; Tan, Jimmy J. M.; Hsu, Lih-Hsing, Hamiltonian circuit and linear array embeddings in faulty \(k\)-ary \(n\)-cubes, Journal of Parallel and Distributed Computing, 67, 4, 362-368 (2007) · Zbl 1115.68032
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.