Find in Library

The augmented cube AQn is an outstanding variation of the hypercube Qn. It possesses many of the favorable properties of Qn as well as some embedded properties not found in Qn. This paper focuses on the fault-tolerant Hamiltonian connectivity of AQn. Under the assumption that F⊂V(AQn)∪E(AQn) with |F|≤2n−3, we proved that for any two different correct vertices u and v in AQn, 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 AQn−F(n≥4). It is worth noting that in this paper we also proved that if there is a weak vertex-pair in AQn−F, there is at most one pair. This paper improved the current result that AQn is 2n−4 fault-tolerant Hamiltonian connected. Our result is optimal and sharp under the condition of no restriction to each vertex.