Upper bound on the size of subgraphs avoiding cycles of girth length in graphs

arXiv:2611.08547v1 Announce Type: new Abstract: A graph $G$ is said to be $H$-free if it contains no copy of $H$. The generalized Tur\'{a}n number $\mathrm{ex}(G, H)$, a natural extension of the classical Tur\'{a}n number, is defined as the maximum number of edges in an $H$-free spanning subgraph of $G$. Although $\mathrm{ex}(G, H)$ has been extensively studied for various specific graphs $G$, such as hypercubes, complete transposition graphs, and doubled Johnson graphs, very few results are known for general graphs. For a graph $G$ of girth $g$, let $C_{g}$ denote the cycle of length $g$. In this paper, we investigate the generalized Tur\'{a}n number $\mathrm{ex}(G, C_{g})$ for graphs $G$ in which every edge is contained in a fixed number of $g$-cycles, and establish a general upper bound on it. This bound generalizes the classical results on hypercubes and provides a unified approach for general graphs. Furthermore, we apply this bound to derive explicit upper bounds for several specific graphs, including $K_{n,n,\ldots,n}$, $K_{n}\times K_{n}$, $C_{m}\times C_{n}$, $S_{n}$, $AG_{n}$, $CT_{n}$ and $J(n;k,k+1)$.

You are being forwarded in 6s — stay on this page