Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of S_n

DOI10.1137/0406012MaRDI QIDQ5285944zbMATHOpenAlexFDO

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

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)

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

Cited in

(31)

• Star transposition Gray codes for multiset permutations
• Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
• Hamiltonian cycles in unitary prefix transposition rearrangement graphs
• Ranking and unranking permutations in linear time
• On a combinatorial generation problem of Knuth
• Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
• Hamilton-connected derangement graphs on \(S_ n\)
• Small matchings extend to Hamiltonian cycles in hypercubes
• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes
• Small cycles, generalized prisms and Hamiltonian cycles in the bubble-sort graph
• A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes
• Towards a problem of Ruskey and Savage on matching extendability
• Matchings extend to Hamiltonian cycles in 5-cube
• MathCheck: a math assistant via a combination of computer algebra systems and SAT solvers
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Extensions to 2-factors in bipartite graphs
• Disjoint Hamilton cycles in the star graph
• Combining SAT solvers with computer algebra systems to verify combinatorial conjectures
• scientific article; zbMATH DE number 4106894 (Why is no real title available?)
• Extending perfect matchings to Hamiltonian cycles in line graphs
• Matching graphs of hypercubes and complete bipartite graphs
• Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle
• The Hamiltonicity of directed \(\sigma\)-\(\tau\) Cayley graphs (Or: A tale of backtracking)
• Rainbow cycles in flip graphs
• Rainbow cycles in flip graphs
• Extending perfect matchings to Gray codes with prescribed ends
• The SAT+CAS method for combinatorial search with applications to best matrices
• Perfect matchings and Hamiltonicity in the Cartesian product of cycles
• On the central levels problem
• A kind of matchings extend to Hamiltonian cycles in hypercubes
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions

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)