2025/07/17 by Da-Wei Yang, Hongyang Zhang, Yang, Da-Wei +5
Computer Science · #Combinatorics (math.CO) #Distributed and Parallel Computing Systems #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2507.12834
openalex publication_date 2025/07/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
This paper focuses on the embeddability of hypercubes in an important class of Cayley graphs, known as augmented cubes. An n-dimensional augmented cube AQn is constructed by augmenting the n-dimensional hypercube Qn with additional edges, thus making Qn a spanning subgraph of AQn. Dong and Wang (2019) first posed the problem of determining the number of Qn-isomorphic subgraphs in AQn, which still remains open. By exploiting the Cayley properties of AQn, we establish a lower bound for this number. What's more, we develop a method for constructing pairs of Qn-isomorphic subgraphs in AQn with the minimum number of common edges. This is accomplished through the use of reciprocal perfect matchings, a technique that also relies on the Cayley property of AQn. As an application, we prove that AQn admits n-1 edge-disjoint Hamiltonian cycles when n≥3 is odd and n-2 cycles when n is even, thereby confirming a conjecture by Hung (2015) for the odd case. Additionally, we prove that AQn has a fault-free cycle of every even length from 4 to 2n with up to 4n-8 faulty edges, when each vertex is incident to at least two fault-free edges. This result not only provides an alternative proof for the fault-tolerant Hamiltonicity of established by Hsieh and Cian (2010), but also extends their work by demonstrating the fault-tolerant bipancyclicity of AQn.