On complete multipartite derangement graphs - Razafimahatratra, Andriaherimanana Sarobidy (Ars mathematica contemporanea, 2021)
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$?. K. Meagher et al. J. Comb. Theory, Ser. A 180, Article ID 105390, 27 p. (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 gves 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$?.
Keywords: Cayley graphs; Cayleyjevi grafi; cocliques; derangement graph; Erdős-Ko-Rado izrek; Erdős-Ko-Rado theorem; koklike; premestitveni graf