Extremal even-cycle-free subgraphs of the $k$-ary $n$-cube

arXiv:2611.05433v1 Announce Type: new Abstract: A graph is said to be $H$-free if it contains no subgraph isomorphic to $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$. For any integer $\ell\geq 2$, let $C_{2\ell}$ denote the even cycle of length $2\ell$. So far, extensive studies of the generalized Tur\'{a}n number for the hypercube $Q_{n}$ have been conducted. The $k$-ary $n$-cube is an important family of graphs with many favorable properties, such as regularity and vertex-transitivity. It generalizes the hypercube and reduces to the hypercube when $k=2$. In this paper, we investigate the generalized Tur\'{a}n number $\mathrm{ex}(Q^{k}_{n}, C_{2\ell})$ of $Q^{k}_{n}$ for all even integers $k\geq 4$ and integers $\ell\geq 2$, generalizing the result for $Q_{n}$ [J. Graph Theory 16 (1992) 273-286] from $k=2$ to $k\geq 4$.

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