Hamilton-connected derangement graphs on \(S_ n\)
type: Item
instance of: scholarly article
title: Hamilton-connected derangement graphs on \(S_ n\)
zbMATH Open document ID: 0808.05069
DOI: 10.1016/0012-365X(94)90028-0
author: David J. Rasmussen
author: Carla D. Savage
published in: Discrete Mathematics
publication date: 1995-03-09T00:00:00Z
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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 681700
zbMATH Keywords: Hamilton-connected
zbMATH Keywords: Hamilton path
zbMATH Keywords: Cayley graph
zbMATH Keywords: symmetric group
zbMATH Keywords: derangement graph
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
cites work: Q3715120
cites work: Hamilton cycles in regular 2-connected graphs
cites work: Generation of Permutations by Adjacent Transposition
cites work: Q3815325
cites work: Generating Permutations with k-Differences
cites work: Q4133641
cites work: Q4190642
cites work: Q4745845
cites work: Connectivity of transitive graphs
cites work: Q3470467
cites work: A survey: Hamiltonian cycles in Cayley graphs
description: scientific article; zbMATH DE number 681700