On triangles in derangement graphs

2020/09/02 by Razafimahatratra, Andriaherimanana Sarobidy, Meagher, Karen, Spiga, Pablo · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2009.01086

Abstract

Given a permutation group G, the derangement graph Γ_G of G is the Cayley graph with connection set the set of all derangements of G. We prove that, when G is transitive of degree at least 3, Γ_G contains a triangle. The motivation for this work is the question of how large can be the ratio of the independence number of Γ_G to the size of the stabilizer of a point in G. We give examples of transitive groups where this ratio is maximum.

Cited by

• The intersection densities of transitive actions of PSL₂(q) with cyclic point stabilizers
• Edge pancyclic Cayley graphs on symmetric group

Related

• On multipartite derangement graphs
• Cliques in derangement graphs for innately transitive groups
• Edge pancyclic Cayley graphs on symmetric group
• Kronecker classes and cliques in derangement graphs
• Properties of Generalized Derangement Graphs