Spectral extremal results on edge blow-up of graphs

Abstract

Let $\mathrm{ex}(n,F)$ and $\mathrm{spex}(n,F)$ be the maximum size and maximum spectral radius of an $F$-free graph of order $n$, respectively. The value $\mathrm{spex}(n,F)$ is called the spectral extremal value of $F$. Nikiforov [J. Graph Theory 62 (2009) 362--368] gave the spectral Stability Lemma, which implies that for every $\epsilon >0$, sufficiently large $n$ and a non-bipartite graph $H$ with chromatic number $\ddot{I}‡(H)$, the extremal graph for $\mathrm{spex}(n,H)$ can be obtained from the Turán graph $T_{\ddot{I}‡(H)-1}(n)$ by adding and deleting at most $\epsilon n^2$ edges. It is still a challenging problem to determine the exact spectral extremal values of many non-bipartite graphs. Given a graph $F$ and an integer $p\ge 2$, the edge blow-up of $F$, denoted by $F^{p+1}$, is the graph obtained from replacing each edge in $F$ by a $K_{p+1}$ where the new vertices of $K_{p+1}$ are all distinct. In this paper, we determine the exact spectral extremal values of the edge blow-up of all non-bipartite graphs and provide the asymptotic spectral extremal values of the edge blow-up of all bipartite graphs for sufficiently large $n$, which can be seen as a spectral version of the theorem on $\mathrm{ex}(n,F^{p+1})$ given by Yuan [J. Combin. Theory Ser. B 152 (2022) 379--398]. As applications, on the one hand, we generalize several previous results on $\mathrm{spex}(n,F^{p+1})$ for $F$ being a matching and a star for $p\ge 3$. On the other hand, we obtain the exact values of $\mathrm{spex}(n,F^{p+1})$ for $F$ being a path, a cycle and a complete graph.