Spectral extremal problem on \(t\) copies of \(\ell\)-cycles

Longfei Fang¹ ; Mingqing Zhai² ; Huiqiu Lin

¹Chuzhou University,Chuzhou, Ahhui, China
²Chuzhou University, Anhui, China

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

Extremal problem on cycles plays an important role in extremal graph theory. Let $ex(n,F)$ and $spex(n,F)$ be the maximum size and spectral radius over all $n$-vertex $F$-free graphs, respectively. In this paper, we shall pay attention to the study of both $ex(n,tC_\ell)$ and $spex(n,tC_\ell)$. On the one hand, we determine $ex(n,tC_{2\ell+1})$ and characterize the extremal graph for any integers $t,\ell$ and $n\geq f(t,\ell)$, where $f(t,\ell)=O(t\ell^2)$. This generalizes the result on $ex(n,tC_3)$ of Erdős [Arch. Math. 13 (1962) 222–227] as well as the research on $ex(n,C_{2\ell+1})$ of Füredi and Gunderson [Combin. Probab. Comput. 24 (2015) 641–645]. On the other hand, motivated by the spectral Turán-type problem proposed by Nikiforov, we obtain the extremal spectral radius $spex(n,tC_{\ell})$ for any fixed $t,\ell$ and large enough $n$. Our results extend some classic spectral extremal results or conjectures on odd cycles and even cycles. Our results also give some inspirations for general spectral Turán-type problem $spex(n,F)$ on bipartite or non-partite $F$.

Détail

DOI : 10.37236/12195

Classification : 05C35, 05C50
Mots-clés : extremal graph theory, spectral extremal problem, Turán number, odd cycles, even cycles, spectral radius