×

Hamiltonian paths passing through prescribed edges in balanced hypercubes. (English) Zbl 1411.68088

Summary: The balanced hypercube was proposed as a novel interconnection network for large-scale parallel systems. It is known that the balanced hypercube is edge-bipancyclic. Given a set of edges \(\mathcal{P}\) with \(| \mathcal{P} | \leq n - 1\) and two vertices \(x\) and \(y\) in different bipartite sets, we show that there exists a Hamiltonian path from \(x\) to \(y\) passing through \(\mathcal{P}\) in \(B H_n\) if and only if \(\mathcal{P}\) is a linear forest and, neither \(x\) nor \(y\) is an internal vertex of \(\mathcal{P}\), and \(x\) and \(y\) are not end-vertices of a component of \(\mathcal{P}\) simultaneously. Consequently, the balanced hypercube contains a Hamiltonian cycle passing through a set \(\mathcal{P}\) of at most \(n\) prescribed edges if and only if \(\mathcal{P}\) is a linear forest. Moreover, our result improves some known results.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C45 Eulerian and Hamiltonian graphs
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001
[2] Caha, R.; Koubek, V., Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. Graph Theory, 51, 2, 137-169 (2006) · Zbl 1084.05041
[3] Chen, D.; Lu, Z.; Shen, Z.; Zhang, G.; Chen, C.; Zhou, Q., Path embeddings with prescribed edge in the balanced hypercube network, Symmetry, 9, 79 (2017) · Zbl 1423.68044
[4] Chen, X.-B., Cycles passing through prescribed edges in a hypercube with some faulty edges, Inform. Process. Lett., 104, 6, 211-215 (2007) · Zbl 1184.68113
[5] Cheng, D.; Hao, R.; Feng, Y., Two node-disjoint paths in balanced hypercubes, Appl. Math. Comput., 242, 127-142 (2014) · Zbl 1334.05070
[6] Dvor̆ák, T., Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math., 19, 1, 135-144 (2005) · Zbl 1082.05056
[7] Dvor̆ák, T.; Gregor, P., Hamiltonian paths with prescribed edges in hypercubes, Discrete Math., 307, 1982-1998 (2007) · Zbl 1119.05060
[8] Hao, R. X.; Ru, Z.; Feng, Y. Q., Hamiltonian cycle embedding for fault tolerance in balanced hypercubes, Appl. Math. Comput., 244, 447-456 (2014) · Zbl 1335.05104
[9] Huang, K.; Wu, J., Fault-tolerant resource placement in balanced hypercubes, Inform. Sci., 99, 159-172 (1997)
[10] Kuo, C.-N.; Chou, H.-H.; Chang, N.-W.; Hsieh, S.-Y., Fault-tolerant path embedding in folded hypercubes with both node and edge faults, Theoret. Comput. Sci., 475, 82-91 (2013) · Zbl 1260.68016
[11] Leighton, F. T., Introduction to Parallel Algorithms and Architectures (1992), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, Calif. · Zbl 0743.68007
[12] Li, J.; Wang, S.; Yang, Y., Panconnectivity and pancyclicity of the 3-ary \(n\)-cube network under the path restrictions, Appl. Math. Comput., 243, 339-348 (2014) · Zbl 1335.68185
[13] Lin, T.-J.; Hsieh, S.-Y.; Juan, J., Embedding cycles and paths in product networks and their applications to multiprocessor systems, IEEE Trans. Parallel Distrib. Syst., 23, 1081-1089 (2012)
[14] Lü, H.; Li, X.; Zhang, H., Matching preclusion for balanced hypercubes, Theoret. Comput. Sci., 465, 10-20 (2012) · Zbl 1254.68188
[15] Lü, H.; Zhang, H., Hyper-Hamiltonian laceability of balanced hypercubes, J. Supercomput., 68, 302-314 (2014)
[16] Lü, H., On extra connectivity and extra edge-connectivity of balanced hypercubes, Int. J. Comput. Math., 94, 813-820 (2016) · Zbl 1362.05072
[17] Lü, H.; Gao, X.; Yang, X., Matching extendability of balanced hypercubes, Ars Combin., 129, 261-274 (2016) · Zbl 1413.05311
[18] Rosenberg, A. L., Issues in the study of graph embedding, (Graph Theoretic Concepts in Computer Science. Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 100 (1981), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, Germany)
[19] Tsai, C.-H., Fault-free cycles passing through prescribed paths in hypercubes with faulty edges, Appl. Math. Lett., 22, 6, 852-855 (2009) · Zbl 1200.05242
[20] Wang, S.; Li, J.; Wang, R., Hamiltonian paths and cycles with prescribed edges in the 3-ary \(n\)-cube, Inform. Sci., 181, 3054-3065 (2011) · Zbl 1218.68110
[21] Wang, S.; Lin, S., Path embeddings in faulty 3-ary \(n\)-cubes, Inform. Sci., 180, 1, 191-197 (2010) · Zbl 1183.68093
[22] Wu, J.; Huang, K., The balanced hypercube: a cube-based system for fault-tolerant applications, IEEE Trans. Comput., 46, 4, 484-490 (1997)
[23] Xu, M.; Hu, H.; Xu, J., Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes, Appl. Math. Comput., 189, 1393-1401 (2007) · Zbl 1161.94012
[24] Yang, M., Bipanconnectivity of balanced hypercubes, Comput. Math. Appl., 60, 1859-1867 (2010) · Zbl 1205.05131
[25] Yang, M., Conditional diagnosability of balanced hypercubes under the PMC model, Inform. Sci., 222, 754-760 (2013) · Zbl 1293.68037
[26] Yang, M., Super connectivity of balanced hypercubes, Appl. Math. Comput., 219, 970-975 (2012) · Zbl 1291.68028
[27] Yang, Y.; Li, J.; Wang, S., Embedding various cycles with prescribed paths into \(k\)-ary \(n\)-cubes, Discrete Appl. Math., 220, 161-169 (2017) · Zbl 1355.05236
[28] Yang, Y.; Wang, S., Fault-free Hamiltonian cycles passing through a linear forest in ternary \(n\)-cubes with faulty edges, Theoret. Comput. Sci., 491, 78-82 (2013) · Zbl 1277.68039
[29] Yang, Y.; Wang, S., A note on Hamiltonian paths and cycles with prescribed edges in the 3-ary \(n\)-cube, Inform. Sci., 296, 42-45 (2015) · Zbl 1407.68377
[30] Zhang, S.; Zhang, X., Fault-free Hamiltonian cycles passing through prescribed edges in \(k\)-ary \(n\)-cubes with faulty edges, IEEE Trans. Parallel Distrib. Syst., 26, 2, 434-443 (2015)
[31] Zhou, J.; Wu, Z.; Yang, S.; Yuan, K., Symmetric property and reliability of balanced hypercube, IEEE Trans. Comput., 64, 3, 876-881 (2015) · Zbl 1360.68181
[32] Zhou, Q.; Chen, D.; Lü, H., Fault-tolerant Hamiltonian laceability of balanced hypercubes, Inform. Sci., 300, 20-27 (2015) · Zbl 1360.68654
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.