Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2507.12834 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909692559622144 |
|---|---|
| author | Yang, Da-Wei Zhang, Hongyang Hao, Rong-Xia Hsieh, Sun-Yuan |
| author_facet | Yang, Da-Wei Zhang, Hongyang Hao, Rong-Xia Hsieh, Sun-Yuan |
| contents | 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_n$ is constructed by augmenting the $n$-dimensional hypercube $Q_n$ with additional edges, thus making $Q_n$ a spanning subgraph of $AQ_n$. Dong and Wang (2019) first posed the problem of determining the number of $Q_n$-isomorphic subgraphs in $AQ_n$, which still remains open. By exploiting the Cayley properties of $AQ_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 $AQ_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 $AQ_n$. As an application, we prove that $AQ_n$ admits $n-1$ edge-disjoint Hamiltonian cycles when $n\geq3$ 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_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 $AQ_n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12834 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity Yang, Da-Wei Zhang, Hongyang Hao, Rong-Xia Hsieh, Sun-Yuan Combinatorics 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_n$ is constructed by augmenting the $n$-dimensional hypercube $Q_n$ with additional edges, thus making $Q_n$ a spanning subgraph of $AQ_n$. Dong and Wang (2019) first posed the problem of determining the number of $Q_n$-isomorphic subgraphs in $AQ_n$, which still remains open. By exploiting the Cayley properties of $AQ_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 $AQ_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 $AQ_n$. As an application, we prove that $AQ_n$ admits $n-1$ edge-disjoint Hamiltonian cycles when $n\geq3$ 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_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 $AQ_n$. |
| title | A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.12834 |