($ 2n-3 $)-fault-tolerant Hamiltonian connectivity of augmented cubes $ AQ_n $
Huifeng Zhang, Xirong Xu, Ziming Wang, Qiang Zhang, Yuansheng Yang · AIMS Mathematics · 2021
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.