On complete multipartite derangement graphs

DOI10.26493/1855-3974.2554.856MaRDI QIDQ5013345zbMATH OpenOpenAlexFDO

Authors A. Sarobidy Razafimahatratra

Publication date 30 November 2021

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

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

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)

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

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.

Cites work

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

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
• Largest independent sets of certain regular subgraphs of the derangement graph
• Cliques in derangement graphs for innately transitive groups
• Intersection density of imprimitive groups of degree \(pq\)
• On the spectrum of derangement graphs of order a product of three primes
• Automorphism group of the derangement graph
• Maximum-size independent sets and automorphism groups of tensor powers of the even derangement graphs
• Complete multipartite graphs that are determined, up to switching, by their Seidel spectrum
• On the intersection density of the Kneser graph \(K(n, 3)\)
• Intersection density of transitive groups of certain degrees
• A note on “Largest independent sets of certain regular subgraphs of the derangement graph”
• 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

Describes a project that uses

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)