Extremal even-cycle-free subgraphs of the complete transposition graphs

Abstract

Given graphs $G$ and $H$, the generalized Turán number $\mathrm{ex}(G,H)$ is the maximum number of edges in an $H$-free subgraph of $G$. In this paper, we obtain an asymptotic upper bound on $\mathrm{ex}(C{T}_n,C_{2l})$ for any $n\ge 3$ and $l\ge 2$, where $C_{2l}$ is the cycle of length $2l$ and $C{T}_n$ is the complete transposition graph which is defined as the Cayley graph on the symmetric group ${\mathrm{S}}_n$ with respect to the set of all transpositions of ${\mathrm{S}}_n$.

16 pages, 1 figure

References in corpus (1)

• On even-cycle-free subgraphs of the doubled Johnson graphs