Geodesic
On complete multipartite derangement graphs
Ars Mathematica Contemporanea, Tome 21 (2021) no. 1, article no. 07, 15 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2554.856
Keywords: Derangement graph, cocliques, Erdős-Ko-Rado theorem, Cayley graphs 
@article{10_26493_1855_3974_2554_856,
     author = {Andriaherimanana Sarobidy Razafimahatratra},
     title = {On complete multipartite derangement graphs},
     journal = {Ars Mathematica Contemporanea},
     eid = {07},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2021},
     doi = {10.26493/1855-3974.2554.856},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2554.856/}
}
TY  - JOUR
AU  - Andriaherimanana Sarobidy Razafimahatratra
TI  - On complete multipartite derangement graphs
JO  - Ars Mathematica Contemporanea
PY  - 2021
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2554.856/
DO  - 10.26493/1855-3974.2554.856
LA  - en
ID  - 10_26493_1855_3974_2554_856
ER  - 
%0 Journal Article
%A Andriaherimanana Sarobidy Razafimahatratra
%T On complete multipartite derangement graphs
%J Ars Mathematica Contemporanea
%D 2021
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2554.856/
%R 10.26493/1855-3974.2554.856
%G en
%F 10_26493_1855_3974_2554_856
Andriaherimanana Sarobidy Razafimahatratra. On complete multipartite derangement graphs. Ars Mathematica Contemporanea, Tome 21 (2021) no. 1, article  no. 07, 15 p. doi : 10.26493/1855-3974.2554.856. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2554.856/

Cité par Sources :