Properties of generalized derangement graphs

DOI10.2140/INVOLVE.2013.6.25MaRDI QIDQ365948zbMATH OpenOpenAlexWikidataFDO

Authors Hannah Jackson, Les Reid, Kathryn Nyman

Publication date 10 September 2013

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.5522

zbMATH Keywords

Cayley graphchromatic numberindependent setderangementsEulerianmaximal clique

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: A permutation sigma in Sn is a k-derangement if for any subset X = {a1, . . ., ak} subseteq [n], {sigma(a1), . . ., sigma(ak)} is not equal to X. One can form the k-derangement graph on the set of permutations of Sn by connecting two permutations sigma and tau if sigma(tau)^-1 is a k-derangement. We characterize when such a graph is connected or Eulerian. For n an odd prime power, we determine the independence, clique and chromatic number of the 2-derangement graph.

Recommendations

• On the spectrum of derangement graphs of order a product of three primes
• Derangement action digraphs and graphs
• A note on \(k\)-derangements
• On complete multipartite derangement graphs
• Largest independent sets of certain regular subgraphs of the derangement graph

Cited in

(14)

• A remarkable connection between \(k\)-permutations and colourings of graphs
• On the disarrangements with \(k\) cycles.
• A note on “Largest independent sets of certain regular subgraphs of the derangement graph”
• Largest independent sets of certain regular subgraphs of the derangement graph
• On complete multipartite derangement graphs
• Derangements on a Ferrers board
• On the spectrum of derangement graphs of order a product of three primes
• A note on \(k\)-derangements
• The territorial raider game and graph derangements
• Setwise intersecting families of permutations
• A note on eigenvalues of the derangement graph.
• Derangement action digraphs and graphs
• 3-setwise intersecting families of the symmetric group
• Generating infinite digraphs by derangements

This page was built for publication: Properties of generalized derangement graphs

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