Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $

DOI10.1137/0406012zbMath0771.05050OpenAlexW2068462604MaRDI QIDQ5285944

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

zbMATH Keywords

permutationsCayley graphHamiltonian graphperfect matchingtranspositionsHamilton cycle

Mathematics Subject Classification ID

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

Related Items (24)

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

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