Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

DOI10.1016/J.DISC.2013.12.014MaRDI QIDQ394540zbMATH OpenOpenAlexFDO

Authors Heping Zhang, Fan Wang

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)