Embedding edge-disjoint Hamiltonian cycles in complete Josephus cubes with applications to fault-tolerant data broadcasting

Ying Gao; Lantao You; Yuejuan Han; Ying Gao; Lantao You; Yuejuan Han

doi:10.3934/math.2026816

AIMS Mathematics

2026, Volume 11, Issue 7: 20085-20102. doi: 10.3934/math.2026816

Previous Article Next Article

Research article

Embedding edge-disjoint Hamiltonian cycles in complete Josephus cubes with applications to fault-tolerant data broadcasting

1.
School of Information Engineering, Suzhou Industrial Park Institute of Services Outsourcing, Suzhou, Jiangsu 215000, China
2.
School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215000, China

Received: 15 April 2026 Revised: 26 June 2026 Accepted: 26 June 2026 Published: 08 July 2026
MSC : 05C38, 05C45

Edge-disjoint Hamiltonian cycles, abbreviated as EDHCs, provide multiple edge-disjoint communication paths for data broadcasting, which greatly enhance the reliability and fault tolerance of data transmission. The complete Josephus cube $ CJC_n $ possesses many desirable properties as a typical interconnection network. In this paper, we focus on the construction of EDHCs in $ CJC_n $. We prove that there exist two EDHCs in $ CJC_n $ when $ n\geq 3 $, and three EDHCs in $ CJC_n $ when $ n\geq 4 $.
- edge-disjoint,
- Hamiltonian cycle,
- complete Josephus cube,
- fault tolerance,
- interconnection network
Citation: Ying Gao, Lantao You, Yuejuan Han. Embedding edge-disjoint Hamiltonian cycles in complete Josephus cubes with applications to fault-tolerant data broadcasting[J]. AIMS Mathematics, 2026, 11(7): 20085-20102. doi: 10.3934/math.2026816

Related Papers:

Abstract

Edge-disjoint Hamiltonian cycles, abbreviated as EDHCs, provide multiple edge-disjoint communication paths for data broadcasting, which greatly enhance the reliability and fault tolerance of data transmission. The complete Josephus cube $ CJC_n $ possesses many desirable properties as a typical interconnection network. In this paper, we focus on the construction of EDHCs in $ CJC_n $. We prove that there exist two EDHCs in $ CJC_n $ when $ n\geq 3 $, and three EDHCs in $ CJC_n $ when $ n\geq 4 $.

References

[1]	M. M. Bae, B. Bose, Edge disjoint Hamiltonian cycles in $k$-ary $n$-cubes and hypercubes, IEEE Trans. Comput., 52 (2003), 1271–1284. https://doi.org/10.1109/TC.2003.1234525 doi: 10.1109/TC.2003.1234525
[2]	R. W. Hung, Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes, Theoret. Comput. Sci., 412 (2011), 4747–4753. https://doi.org/10.1016/j.tcs.2011.05.004 doi: 10.1016/j.tcs.2011.05.004
[3]	R. W. Hung, C. C. Liao, Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes, IAENG Int. J. Comput. Sci., 39 (2012), 42–49. Available from: https://api.semanticscholar.org/CorpusID: 18927068.
[4]	R. W. Hung, The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks, Discrete Appl. Math., 181 (2015), 109–122. https://doi.org/10.1016/j.dam.2014.09.006 doi: 10.1016/j.dam.2014.09.006
[5]	K. J. Pai, Two edge-disjoint Hamiltonian cycles in shuffle-cubes, ICS 2024, 2024, 41–46. https://doi.org/10.1109/ICS64339.2024.00016
[6]	D. Yang, Z. Xu, Y. Feng, J. Lee, Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube, Appl. Math. Comput., 452 (2023), 128075. https://doi.org/10.1016/j.amc.2023.128075 doi: 10.1016/j.amc.2023.128075
[7]	K. J. Pai, R. Y. Wu, S. L. Peng, J. M. Chang, Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcasting, J. Supercomput.‌, 79 (2023), 4126–4145. https://doi.org/10.1007/s11227-022-04825-5 doi: 10.1007/s11227-022-04825-5
[8]	K. J. Pai, Embedding three edge-disjoint Hamiltonian cycles into locally twisted cubes, COCOON 2021, 13025 (2021), 367–374. https://doi.org/10.1007/978-3-030-89543-3_31 doi: 10.1007/978-3-030-89543-3_31
[9]	K. J. Pai, Three edge-disjoint Hamiltonian cycles in folded locally twisted cubes and folded crossed cubes with applications to all-to-all broadcasting, Mathematics, 11 (2023), 3384. https://doi.org/10.3390/math11153384 doi: 10.3390/math11153384
[10]	H. Lv, T. Wu, Edge-disjoint Hamiltonian cycles of balanced hypercubes, Inf. Process. Lett., 144 (2019), 25–30. https://doi.org/10.1016/j.ipl.2018.12.004 doi: 10.1016/j.ipl.2018.12.004
[11]	S. Liu, Y. Wang, J. Fan, B. Cheng, Edge-disjoint Hamiltonian cycles in balanced hypercubes with applications to fault-tolerant data broadcasting, Int. J. Found. Comput. Sci., 36 (2025), 1–24. https://doi.org/10.1142/S0129054124500047 doi: 10.1142/S0129054124500047
[12]	Y. Saad, M. H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput., 37 (1988), 867–872. https://doi.org/10.1109/12.2234 doi: 10.1109/12.2234
[13]	P. K. K. Loh, W. Hsu, The Josephus cube: a novel interconnection network, ‌Parallel Comput., 26 (2000), 427–453. https://doi.org/10.1016/S0167-8191(99)00111-8 doi: 10.1016/S0167-8191(99)00111-8
[14]	Z. Huang, Y. Yang, M. Zhang, X. Yang, Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivity, ‌J. Supercomput., 81 (2025), 180. https://doi.org/10.1007/s11227-024-06564-1 doi: 10.1007/s11227-024-06564-1
[15]	Z. Huang, M. Zhang, C. W. Lee, Connectivity and diagnosability of the complete Josephus cube networks under $h$-extra fault-tolerant model, Theoret. Comput. Sci., 1020 (2024), 114925. https://doi.org/10.1016/j.tcs.2024.114925 doi: 10.1016/j.tcs.2024.114925
[16]	Q. He, Y. Wang, J. Fan, B. Cheng, Vertex-independent spanning trees in complete Josephus cubes, Theoret. Comput. Sci., 1025 (2025), 114969. https://doi.org/10.1016/j.tcs.2024.114969 doi: 10.1016/j.tcs.2024.114969
[17]	Q. He, Y. Wang, J. Fan, B. Cheng, Parallel construction of edge-independent spanning trees in complete Josephus cubes, ‌J. Supercomput., 81 (2025), 334. https://doi.org/10.1007/s11227-024-06784-5 doi: 10.1007/s11227-024-06784-5
[18]	S. Liu, Z. Huang, Y. Lv, C. W. Lee, Evaluating the reliability of complete Josephus cubes under extra link fault with the optimal solution of the edge isoperimetric problem, Theoret. Comput. Sci., 1030 (2025), 115064. https://doi.org/10.1016/j.tcs.2025.115064 doi: 10.1016/j.tcs.2025.115064
[19]	Y. Yang, Z. Huang, M. Zhang, J. Meng, Edge isoperimetric method for link fault tolerance of the complete Josephus cube under five models: a unified approach, Discrete Appl. Math., 378 (2026), 27–36. https://doi.org/10.1016/j.dam.2025.06.043 doi: 10.1016/j.dam.2025.06.043

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)