Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

DOI10.1016/J.DISC.2013.12.014zbMATH Open1281.05100arXiv1301.2931OpenAlexW2129394762MaRDI QIDQ394540FDOQ394540

Authors: Heping Zhang, Fan Wang 

Publication date: 27 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Ruskey and Savage asked the following question: Does every matching of $Q_n$ for $ngeq2$ extend to a Hamiltonian cycle of $Q_n$? J. Fink showed that the question is true for every perfect matching, and solved the Kreweras' conjecture. In this paper we consider the question in hypercubes with faulty edges. We show that every matching $M$ of at most $2n-1$ edges can be extended to a Hamiltonian cycle of $Q_n$ for $ngeq2$. Moreover, we can prove that when $ngeq4$ and $M$ is nonempty this result still holds even if $Q_n$ has at most $n-1-lceilfrac|M|2ceil$ faulty edges with one exception.

Full work available at URL: https://arxiv.org/abs/1301.2931

Recommendations

• Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
• Small matchings extend to Hamiltonian cycles in hypercubes
• Two types of matchings extend to Hamiltonian cycles in hypercubes.
• Matchings of quadratic size extend to long cycles in hypercubes
• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes

zbMATH Keywords

matchinghypercubeHamiltonian cycleedge fault-tolerance

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
• Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes
• Graph theory with applications
• Title not available (Why is that?)
• A survey of the theory of hypercube graphs
• Hamiltonian Cycles with Prescribed Edges in Hypercubes
• A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges
• On ring embedding in hypercubes with faulty nodes and links
• A Survey of Combinatorial Gray Codes
• Perfect matchings extend to Hamilton cycles in hypercubes
• On the Existence of Hamiltonian Circuits in Faulty Hypercubes
• Matching graphs of hypercubes and complete bipartite graphs
• On Hamiltonian circuits and spanning trees of hypercubes
• Hamiltonian fault-tolerance of hypercubes
• Title not available (Why is that?)
• Matching Extendability in Hypercubes
• Title not available (Why is that?)
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $

Cited In (8)

• Small matchings extend to Hamiltonian cycles in hypercubes
• Two types of matchings extend to Hamiltonian cycles in hypercubes.
• Extending pairings to Hamiltonian cycles
• Matchings of quadratic size extend to long cycles in hypercubes
• Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
• A kind of matchings extend to Hamiltonian cycles in hypercubes
• Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
• Extending perfect matchings to Gray codes with prescribed ends

This page was built for publication: Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394540)