A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity

Abstract

This paper focuses on the embeddability of hypercubes in an important class of Cayley graphs, known as augmented cubes. An $n$-dimensional augmented cube $A{Q}_n$ is constructed by augmenting the $n$-dimensional hypercube $Q_n$ with additional edges, thus making $Q_n$ a spanning subgraph of $A{Q}_n$. Dong and Wang (2019) first posed the problem of determining the number of $Q_n$-isomorphic subgraphs in $A{Q}_n$, which still remains open. By exploiting the Cayley properties of $A{Q}_n$, we establish a lower bound for this number. What's more, we develop a method for constructing pairs of $Q_n$-isomorphic subgraphs in $A{Q}_n$ 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 $A{Q}_n$. As an application, we prove that $A{Q}_n$ admits $n-1$ edge-disjoint Hamiltonian cycles when $n\ge 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 $A{Q}_n$ has a fault-free cycle of every even length from $4$ to $2^n$ 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 $A{Q}_n$.