Hamilton-connected derangement graphs on \(S_ n\) (Q1336702): Difference between revisions

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.