Answers are grounded in this paper and cite their sources.
This analysis establishes lower bounds for hypercube embeddability in augmented cubes, suggesting new methods for Hamiltonian decomposition.
This paper focuses on the embeddability of hypercubes in an important class of Cayley graphs, known as augmented cubes. An n-dimensional augmented cube AQₙ is constructed by augmenting the n-dimensional hypercube Qₙ with additional edges, thus making Qₙ a spanning subgraph of AQₙ. Dong and Wang (2019) first posed the problem of determining the number of Qₙ-isomorphic subgraphs in AQₙ, which still remains open. By exploiting the Cayley properties of AQₙ, we establish a lower bound for this number. What's more, we develop a method for constructing pairs of Qₙ-isomorphic subgraphs in AQₙ 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 AQₙ. As an application, we prove that AQₙ 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 AQₙ has a fault-free cycle of every even length from $4$ to 2ⁿ 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 AQₙ.
No takes yet. Share an insight, caveat, or question.
Yang et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: