• Andriaherimanana Sarobidy RazafimahatratraUniversity of Regina, Canadahttps://orcid.org/0000-0002-3542-9160

DOI:

Keywords:

Abstract

Given a finite transitive permutation groupG≤Sym(Ω), with |Ω| ≥ 2, the derangement graphΓ_G ofG is the Cayley graph Cay (G,Der(G)), where Der(G) is the set of all derangements ofG. 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 ifp is an odd prime andG is a transitive group of degree 2p, then the independence number ofΓ_G is at most twice the size of a point-stabilizer ofG.