Largest independent sets of certain regular subgraphs of the derangement graph

DOI10.1007/s10801-015-0656-4zbMath1342.05101OpenAlexW2293688497MaRDI QIDQ737973

Cheng Yeaw Ku, Kok Bin Wong, Terry Shue Chien Lau

Publication date: 12 August 2016

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10801-015-0656-4

zbMATH Keywords

Cayley graphderangement graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Symmetric groups (20B30)

Related Items (5)

Eigenvalues of the matching derangement graph ⋮ Eigenvalues of Cayley graphs ⋮ The spectrum of eigenvalues for certain subgraphs of the \(k\)-point fixing graph ⋮ Alternating sign property of the perfect matching derangement graph ⋮ On the partition associated to the smallest eigenvalues of the \(k\)-point fixing graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs
• Spectrum of Cayley graphs on the symmetric group generated by transpositions
• Intersecting families in the alternating group and direct product of symmetric groups
• Eigenvalues of the derangement graph
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the spectrum of the derangement graph
• Arrangement graphs: A class of generalized star graphs
• Spectra of Cayley graphs
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Stable sets of maximal size in Kneser-type graphs
• Cayley graph on symmetric group generated by elements fixing \(k\) points
• On the eigenvalues of certain Cayley graphs and arrangement graphs
• Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
• A proof of the Cameron-Ku conjecture
• Generating a random permutation with random transpositions
• Intersecting families of permutations
• Intersecting families of permutations

This page was built for publication: Largest independent sets of certain regular subgraphs of the derangement graph