On complete multipartite derangement graphs

DOI10.26493/1855-3974.2554.856zbMATH Open1479.05147arXiv2102.05250OpenAlexW3151856772MaRDI QIDQ5013345FDOQ5013345

Authors: A. Sarobidy Razafimahatratra 

Publication date: 30 November 2021

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: Given a finite transitive permutation group $GleqoperatornameSym(Omega)$, with $|Omega|geq2$, the derangement graph $Gamm{a}_G$ of $G$ is the Cayley graph $operatornameCay(G,operatornameDer(G))$, where $operatornameDer(G)$ is the set of all derangements of $G$. Meagher et al. [On triangles in derangement graphs, {it J. Combin. Theory Ser. A}, 180:105390, 2021] recently proved that $operatornameSym(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 $Gamm{a}_G$ is at most twice the size of a point-stabilizer of $G$.

Full work available at URL: https://arxiv.org/abs/2102.05250

Recommendations

• On triangles in derangement graphs
• Automorphism group of the derangement graph
• Properties of generalized derangement graphs
• On the spectrum of derangement graphs of order a product of three primes
• Transitive permutation groups in which all derangements are involutions.

zbMATH Keywords

derangement graphcocliquesErdős-Ko-Rado theoremCayley graphs.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) General theory for finite permutation groups (20B05) Extremal set theory (05D05)

Cites Work

• Homomorphisms of 3-chromatic graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On a theorem of Jordan
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• Stable sets of maximal size in Kneser-type graphs
• A new proof for the Erdős-Ko-Rado theorem for the alternating group
• An Erdős-Ko-Rado theorem for finite 2-transitive groups
• Erdős-Ko-Rado theorems. Algebraic approaches
• The Erdős-Ko-Rado property for some permutation groups
• Intersecting families of permutations
• An Erdős-Ko-Rado theorem for the derangement graph of PGL(\(2,q\)) acting on the projective line
• The exact bound in the Erdős-Ko-Rado theorem
• The Erdős-Ko-Rado property for some 2-transitive groups
• Erdös–Ko–Rado Theorem—22 Years Later
• The Erdős-Ko-Rado theorem for vector spaces
• Intersecting families of permutations
• 3-setwise intersecting families of the symmetric group
• The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective space
• On triangles in derangement graphs

Cited In (17)

• On the intersection density of primitive groups of degree a product of two odd primes
• On maximum intersecting sets in direct and wreath product of groups
• On the intersection density of the symmetric group acting on uniform subsets of small size
• Cliques in derangement graphs for innately transitive groups
• Intersection density of imprimitive groups of degree \(pq\)
• Largest independent sets of certain regular subgraphs of the derangement graph
• On the spectrum of derangement graphs of order a product of three primes
• Maximum-size independent sets and automorphism groups of tensor powers of the even derangement graphs
• Automorphism group of the derangement graph
• Complete multipartite graphs that are determined, up to switching, by their Seidel spectrum
• On the intersection density of the Kneser graph \(K(n, 3)\)
• A note on “Largest independent sets of certain regular subgraphs of the derangement graph”
• Intersection density of transitive groups of certain degrees
• On intersection density of transitive groups of degree a product of two odd primes
• Intersection density of cubic symmetric graphs
• Intersection density of transitive groups with small cyclic point stabilizers
• Properties of generalized derangement graphs

Uses Software

• SageMath

This page was built for publication: On complete multipartite derangement graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013345)