($ 2n-3 $)-fault-tolerant Hamiltonian connectivity of augmented cubes $ AQ_n $

Huifeng Zhang; Xirong Xu; Ziming Wang; Qiang Zhang; Yuansheng Yang; Huifeng Zhang; Xirong Xu; Ziming Wang; Qiang Zhang; Yuansheng Yang

doi:10.3934/math.2021208

AIMS Mathematics

2021, Volume 6, Issue 4: 3486-3511. doi: 10.3934/math.2021208

Previous Article Next Article

Research article

($ 2n-3 $)-fault-tolerant Hamiltonian connectivity of augmented cubes $ AQ_n $

School of Computer Science and Technology, Dalian University of Technology, Dalian, 116024, China

Received: 14 November 2020 Accepted: 06 January 2021 Published: 21 January 2021
MSC : 05C38, 68M15

The augmented cube $ AQ_n $ is an outstanding variation of the hypercube $ Q_n $. It possesses many of the favorable properties of $ Q_n $ as well as some embedded properties not found in $ Q_n $. This paper focuses on the fault-tolerant Hamiltonian connectivity of $ AQ_n $. Under the assumption that $ F\subset V(AQ_n)\cup E(AQ_n) $ with $ |F|\leq 2n-3 $, we proved that for any two different correct vertices $ u $ and $ v $ in $ AQ_n $, there exists a fault-free Hamiltonian path that joins vertices $ u $ and $ v $ with the exception of $ (u, v) $, which is a weak vertex-pair in $ AQ_n-F $($ n\geq4 $). It is worth noting that in this paper we also proved that if there is a weak vertex-pair in $ AQ_n-F $, there is at most one pair. This paper improved the current result that $ AQ_n $ is $ 2n-4 $ fault-tolerant Hamiltonian connected. Our result is optimal and sharp under the condition of no restriction to each vertex.
- network topological structure,
- graph theory,
- augmented cube $ AQ_n $,
- computer network reliability,
- fault tolerance,
- Hamiltonian connectivity
Citation: Huifeng Zhang, Xirong Xu, Ziming Wang, Qiang Zhang, Yuansheng Yang. ($ 2n-3 $)-fault-tolerant Hamiltonian connectivity of augmented cubes $ AQ_n $[J]. AIMS Mathematics, 2021, 6(4): 3486-3511. doi: 10.3934/math.2021208

Related Papers:

Abstract

The augmented cube $ AQ_n $ is an outstanding variation of the hypercube $ Q_n $. It possesses many of the favorable properties of $ Q_n $ as well as some embedded properties not found in $ Q_n $. This paper focuses on the fault-tolerant Hamiltonian connectivity of $ AQ_n $. Under the assumption that $ F\subset V(AQ_n)\cup E(AQ_n) $ with $ |F|\leq 2n-3 $, we proved that for any two different correct vertices $ u $ and $ v $ in $ AQ_n $, there exists a fault-free Hamiltonian path that joins vertices $ u $ and $ v $ with the exception of $ (u, v) $, which is a weak vertex-pair in $ AQ_n-F $($ n\geq4 $). It is worth noting that in this paper we also proved that if there is a weak vertex-pair in $ AQ_n-F $, there is at most one pair. This paper improved the current result that $ AQ_n $ is $ 2n-4 $ fault-tolerant Hamiltonian connected. Our result is optimal and sharp under the condition of no restriction to each vertex.

References

[1]	C. M. Lee, Y. H. Teng, J. J. M. Tan, L. H. Hsu, Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position, Comput. Math. Appl., 58 (2009), 1762–1768. doi: 10.1016/j.camwa.2009.07.079
[2]	D. Zhou, J. Fan, C. K. Lin, J. Zhou, X. Wang, Cycles embedding in exchanged crossed cube, Int. J. Found. Comput. Sci., 28 (2017), 61–76. doi: 10.1142/S0129054117500058
[3]	H. C. Hsu, L. C. Chiang, J. J. M. Tan, L. H. Hsu, Fault Hamiltonicity of augmented cubes, Parallel Comput., 31 (2005), 131–145. doi: 10.1016/j.parco.2004.10.002
[4]	H. Wang, J. Wang, J. M. Xu, Fault-tolerant panconnectivity of augmented cubes, Frontiers Math. China, 4 (2009), 697–719. doi: 10.1007/s11464-009-0042-4
[5]	J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parallel Distrib. Syst., 16 (2005), 1190–1200. doi: 10.1109/TPDS.2005.151
[6]	J. Fan, X. Jia, X. Lin, Optimal embeddings of paths with various lengths in twisted cubes, IEEE Trans. Parallel Distrib. Syst., 18 (2007), 511–521. doi: 10.1109/TPDS.2007.1003
[7]	J. Fan, X. Lin, Y. Pan, X. Jia, Optimal fault-tolerant embedding of paths in twisted cubes, J. Parallel Distrib. Comput., 67 (2007), 205–214. doi: 10.1016/j.jpdc.2006.04.004
[8]	J. Fan, X. Jia, Embedding meshes into crossed cubes, Inf. Sci., 177 (2007), 3151–3160. doi: 10.1016/j.ins.2006.12.010
[9]	X. Wang, J. Fan, X. Jia, S. Zhang, J. Yu, Embedding meshes into twisted-cubes, Inf. Sci., 181 (2011), 3085–3099. doi: 10.1016/j.ins.2011.02.019
[10]	J. Xu, M. Ma, A survey on cycle and path embedding in some networks, Frontiers Math. China, 4 (2009), 217–252. doi: 10.1007/s11464-009-0017-5
[11]	M. Ma, G. Liu, J. M. Xu, Fault-tolerant embedding of paths in crossed cubes, Theor. Comput. Sci., 407 (2008), 110–116. doi: 10.1016/j.tcs.2008.05.002
[12]	M. Ma, G. Liu, J. M. Xu, The super connectivity of augmented cubes, Inf. Process. Lett., 106 (2008), 59–63. doi: 10.1016/j.ipl.2007.10.005
[13]	M. Xu, J. M. Xu, The forwarding indices of augmented cubes, Inf. Process. Lett., 101 (2007), 185–189. doi: 10.1016/j.ipl.2006.09.013
[14]	M. Ma, G. Liu, J. M. Xu, Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Comput., 33 (2007), 36–42. doi: 10.1016/j.parco.2006.11.008
[15]	P. Kulasinghe, S. Bettayeb, Embedding binary trees into crossed cubes, IEEE Trans. Comput., 44 (1995), 923–929. doi: 10.1109/12.392850
[16]	S. A. Choudum, V. Sunitha, Augmented cubes, Networks, 40 (2002), 71–84.
[17]	S. A. Choudum, V. Sunitha, Distance and short parallel paths in augmented cubes, Electron. Notes Discrete Math., 15 (2003), 64. doi: 10.1016/S1571-0653(04)00532-3
[18]	S. A. Choudum, V. Sunitha, Wide-diameter of augmented cubes, Technical Report, Department of Mathematics, Indian Institute of Technology Madras, Chennai, 2000.
[19]	S. A. Choudum, V. Sunitha, Automorphisms of augmented cubes, Technical Report, Department of Mathematics, Indian Institute of Technology Madras, Chennai, 2001.
[20]	W. W. Wang, M. J. Ma, J. M. Xu, Fault-tolerant pancyclicity of augmented cubes, Inf. Process. Lett., 103 (2007), 52–56. doi: 10.1016/j.ipl.2007.02.012
[21]	W. C. Fang, C. C. Hsu, C. M. Wang, On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks, Inf. Sci., 151 (2003), 51–70. doi: 10.1016/S0020-0255(02)00389-4
[22]	X. Xu, H. Zhang, S. Zhang, Y. Yang, Fault-tolerant panconnectivity of augmented cubes $AQ_n$, Int. J. Found. Comput. Sci., 30 (2019), 1247–1278. doi: 10.1142/S0129054119500254
[23]	H. Zhang, X. Xu, J. Guo, Y. Yang, Fault-tolerant Hamiltonian-connectivity of twisted hypercube-like networks THLNs, IEEE Access, 6 (2018), 74081–74090. doi: 10.1109/ACCESS.2018.2882520
[24]	H. Zhang, X. Xu, Q. Zhang, Y. Yang, Fault-tolerant path-embedding of twisted hypercube-like networks (THLNs), Mathematics, 7 (2019), 1066. doi: 10.3390/math7111066
[25]	N. Ascheuer, Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems, PhD thesis, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 1996.
[26]	N. C. Wang, C. P. Yan, C. P. Chu, Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model, J. Syst. Archit., 51 (2005), 165–183. doi: 10.1016/j.sysarc.2004.11.001
[27]	X. Lin, P. K. McKinley, L. M. Li, Deadlock-free multicast wormhole routing in 2-D mesh multiprocessors, IEEE Trans. Parallel Distrib. Syst., 5 (1994), 793–804. doi: 10.1109/71.298203

Reader Comments

Your name:*

Email:*
© 2021 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)