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.
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.
