On complete multipartite derangement graphs

Andriaherimanana Sarobidy Razafimahatratra


Given a finite transitive permutation group G≤Sym(Ω), with |Ω| ≥ 2, the derangement graph ΓG of G is the Cayley graph Cay (G,Der(G)), where Der(G) is the set of all derangements of G. Meagher et al. [On triangles in derangement graphs, J. Combin. Theory Ser. A, 180:105390, 2021] recently proved that Sym(2) acting on {1, 2} is the only transitive group whose derangement graph is bipartite and any transitive group of degree at least three has a triangle in its derangement graph. They also showed that there exist transitive groups whose derangement graphs are complete multipartite.

This paper gives two new families of transitive groups with complete multipartite derangement graphs. In addition, we prove that if p is an odd prime and G is a transitive group of degree 2p, then the independence number of ΓG is at most twice the size of a point-stabilizer of G.


Derangement graph, cocliques, Erdős-Ko-Rado theorem, Cayley graphs

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2554.856

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications