Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of S_n

DOI10.1137/0406012zbMATH Open0771.05050OpenAlexW2068462604MaRDI QIDQ5285944FDOQ5285944

Authors: Frank Ruskey, Carla D. Savage 

Publication date: 29 June 1993

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

Full work available at URL: https://doi.org/10.1137/0406012

Recommendations

• Hamiltonian cycles in n‐extendable graphs
• Hamilton cycles in some vertex-transitive graphs
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• Matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes
• Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
• Hamiltonian cycles in normal Cayley graphs
• A survey: Hamiltonian cycles in Cayley graphs
• A survey: Hamiltonian cycles in Cayley graphs
• The edge transitivity and Hamiltonian property of a class of Cayley graphs
• scientific article; zbMATH DE number 1488865

zbMATH Keywords

permutationsCayley graphHamilton cycleperfect matchingHamiltonian graphtranspositions

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (29)

• Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
• Extending perfect matchings to Hamiltonian cycles in line graphs
• Extensions to 2-factors in bipartite graphs
• Combining SAT solvers with computer algebra systems to verify combinatorial conjectures
• Small matchings extend to Hamiltonian cycles in hypercubes
• Matching graphs of hypercubes and complete bipartite graphs
• Rainbow Cycles in Flip Graphs.
• Rainbow Cycles in Flip Graphs
• MathCheck: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers
• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes
• A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes
• Perfect matchings and Hamiltonicity in the Cartesian product of cycles
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• Disjoint Hamilton cycles in the star graph
• Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle
• Star transposition Gray codes for multiset permutations
• Title not available (Why is that?)
• Hamilton-connected derangement graphs on \(S_ n\)
• On a Combinatorial Generation Problem of Knuth
• The SAT+CAS method for combinatorial search with applications to best matrices
• Towards a problem of Ruskey and Savage on matching extendability
• Matchings extend to Hamiltonian cycles in 5-cube
• The Hamiltonicity of directed \(\sigma\)-\(\tau\) Cayley graphs (Or: A tale of backtracking)
• On the central levels problem
• A kind of matchings extend to Hamiltonian cycles in hypercubes
• Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
• Ranking and unranking permutations in linear time
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Extending perfect matchings to Gray codes with prescribed ends

This page was built for publication: Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $

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