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

MAKE IMPACT

Da-Wei Yang , Hongyang Zhang , Rong‐Xia Hao , Sun‐Yuan Hsieh · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2507.12834

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$.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2507.12834

PDF

https://arxiv.org/pdf/2507.12834

OA Status

green

OpenAlex ID

https://openalex.org/W4415309890

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4415309890

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2507.12834

Digital Object Identifier

Title

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

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2025

Year of publication

Publication date

2025-07-17

Full publication date if available

Authors

Da-Wei Yang, Hongyang Zhang, Rong‐Xia Hao, Sun‐Yuan Hsieh

List of authors in order

Landing page

https://arxiv.org/abs/2507.12834

Publisher landing page

PDF URL

https://arxiv.org/pdf/2507.12834

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2507.12834

Direct OA link when available

Cited by

0

Total citation count in OpenAlex

Full payload