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.

Meagher, K., Razafimahatratra, A., Spiga, P. (2021). On triangles in derangement graphs. JOURNAL OF COMBINATORIAL THEORY. SERIES A, 180(May 2021) [10.1016/j.jcta.2020.105390].

On triangles in derangement graphs

Spiga P.
2021

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.
Articolo in rivista - Articolo scientifico
Derangement graph; Erdős-Ko-Rado Theorem; Independent sets; Multipartite graphs; Symmetric group;
English
29-dic-2020
2021
180
May 2021
105390
open
Meagher, K., Razafimahatratra, A., Spiga, P. (2021). On triangles in derangement graphs. JOURNAL OF COMBINATORIAL THEORY. SERIES A, 180(May 2021) [10.1016/j.jcta.2020.105390].
File in questo prodotto:
File Dimensione Formato  
Spiga-2021-J Comb Theory A-preprint.pdf

accesso aperto

Descrizione: Research Article
Tipologia di allegato: Submitted Version (Pre-print)
Licenza: Creative Commons
Dimensione 292.01 kB
Formato Adobe PDF
292.01 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/415964
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
Social impact