Hamilton-connected derangement graphs on S_ n

DOI10.1016/0012-365X(94)90028-0MaRDI QIDQ1336702zbMATH OpenFDO

Authors David J. Rasmussen, Carla D. Savage

Publication date 9 March 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)90028-0

zbMATH Keywords

Cayley graphderangement graphHamilton pathHamilton-connectedsymmetric group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

A graph \(X\) is said to be Hamilton-connected if for any two vertices \(u\) and \(v\) of \(X\) there is a Hamilton path whose terminal vertices are \(u\) and \(v\). Given a group \(G\) and a set \(S\subset G\) such that \(S=S^{-1}\) and \(1\not\in S\), the Cayley graph \(X(G;S)\) on \(G\) with symbol \(S\) has the elements of \(G\) as its vertex set and an edge joining \(g\) and \(h\) if and only if \(g^{-1}h\in S\). Let \(S_ n\) denote the symmetric group of degree \(n\) and \(D\) be the set of derangements in \(S_ n\). The Cayley graph \(X(S_ n;D)\) is called a derangement graph. The authors prove that \(X(S_ n;D)\) is Hamilton-connected for all \(n\geq4\). They obtain a similar result for a family of Cayley graphs they call \(k\)-consecutive derangement graphs.

Recommendations

• Hamilton-connected Cayley graphs on Hamiltonian groups
• Cayley graphs and interchange graphs
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Hamilton paths in Cayley graphs on Coxeter groups. I.
• Derangement action digraphs and graphs

Cites work

• A survey: Hamiltonian cycles in Cayley graphs
• Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
• Connectivity of transitive graphs
• Generating Permutations with k-Differences
• Generation of Permutations by Adjacent Transposition
• Hamilton cycles in regular 2-connected graphs
• scientific article; zbMATH DE number 4137767 (Why is no real title available?)
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 4085685 (Why is no real title available?)
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 3628955 (Why is no real title available?)
• scientific article; zbMATH DE number 3801574 (Why is no real title available?)

Cited in

(7)

• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Derangement action digraphs and graphs
• Cayley graphs and interchange graphs
• Hamiltonian cycles in unitary prefix transposition rearrangement graphs
• Enumerative and structural aspects of anagrams without fixed letters
• Generating all invertible matrices by row operations
• Generating all invertible matrices by row operations

This page was built for publication: Hamilton-connected derangement graphs on \(S_ n\)

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