Shuchao Li

Given a graph $H$, a graph is said to be $H$-free if it does not contain $H$ as a subgraph. A graph is color-critical when it has an edge whose removal leads to a reduction in its chromatic number. For a graph $H$ with a chromatic number of \(r + 1\), we use \(\text{spex}_{r + 1}(n, H)\) to represent the maximum spectral radius among non-$r$-partite $H$-free graphs of order $n$. The set of all non-$r$-partite $H$-free graphs of order $n$ that have a spectral radius of \(\text{spex}_{r + 1}(n, H)\) is denoted as \(\text{SPEX}_{r + 1}(n, H)\). For \(r\geq2\) and \(k\geq1\), we define \(B_{r,k}\) as the graph constructed by connecting each vertex of \(K_r\) to every vertex of an independent set with size $k$. We refer to \(B_{r,k}\) as a book graph (in the case of \(r = 2\)) or a generalized book graph (when \(r\geq3\)). It should be noted that \(B_{r,k}\) is a color-critical graph with a chromatic number of \(r + 1\). Lin, Ning, and Wu (2021) identified the unique extremal graph within \(\text{SPEX}_3(n, B_{2,1})\); Li and Peng (2023) determined the unique extremal graph in \(\text{SPEX}_{r + 1}(n, B_{r,1})\) for all \(r\geq2\). Quite recently, Liu and Miao (2025) specified the unique extremal graph in \(\text{SPEX}_3(n, B_{2,k})\) for all \(k\geq2\). Inspired by these remarkable results, this paper, relying on spectral stability theory, local structure characterization, along with the theory of characteristic equations and Rayleigh quotient equations, aims to determine the unique extremal graph in \(\text{SPEX}_{r + 1}(n, B_{r,k})\) for \(r\geq3\), \(k\geq1\), and sufficiently large $n$. This work partially addresses an open problem put forward in [38].

Given a graph $H,$ we say that a graph is \textit{$H$-free} if it does not contain $H$ as a subgraph. The Turán number $\ex(n,H)$ of $H$ is the maximum number of edges in an $n$-vertex $H$-free graph, the set of all the corresponding extremal graphs is denoted by $\Ex(n, H)$. The study of Turán number of graphs is a central topic in extremal graph theory. A graph is \textit{color-critical} if it contains an edge whose deletion reduces its chromatic number. Simonovits showed that if $H$ is a color-critical graph of chromatic number $r+1,$ then for sufficiently large $n,$ $\Ex(n, H)=\{T_r(n)\},$ the $r$-partite Turán graph of order $n.$ Given a color-critical graph $H$ with chromatic number $r+1,$ it is interesting to determine $H$-free non-$r$-partite graphs with maximum number of edges. For a graph $H$ with chromatic number $r+1,$ denote $\ex_{r+1}(n,H)$ the maximum number of edges in non-$r$-partite $H$-free graphs of order $n,$ the set of all non-$r$-partite $H$-free graphs of order $n$ and size $\ex_{r+1}(n,H)$ is denoted by $\Ex_{r+1}(n, H)$. For $r\geq 3,\,k\geq1,$ the generalized book graph \({B}_{r,k}\) is a graph obtained by joining every vertex of $K_r$ to every vertex of an independent set of size \(k\). Note that \({B}_{r,k}\) is a color-critical graph of chromatic number $r+1.$ In this paper, based on the stability theory and local structure characterization, the exact value of $\ex_{r+1}(n,B_{r,k})$ is determined and all the corresponding extremal graphs are identified, where $r\geq 3,\,k\geq1$ and $n$ is sufficiently large.

For a graph $G$ and a real number $\alpha\in [0,1],$ Nikiforov (2017) proposed the $A_\alpha$-matrix for $G,$ which is defined as $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$, where $A(G)$ and $D(G)$ are the adjacency matrix and the degree diagonal matrix of $G$, respectively. The largest eigenvalue of $A_{\alpha}(G)$ is called the $A_\alpha$-index of $G.$ Let $\mathcal{F}$ be a set of graphs, we say a graph $G$ is $\mathcal{F}$-free if it does not contain a member in $\mathcal{F}$ as a subgraph. In 2010, Nikiforov conjectured that for $n$ large enough, the $\{C_{2k+1}, C_{2k+2}\}$-free graph of maximum spectral radius is $S_{n,k}$, the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and that the $C_{2k+2}$-free graph of maximum spectral radius is $S_{n,k}^+$, the graph obtained from $S_{n,k}$ by adding one edge. Cioabă, Desai and Tait (2022) used a novel method to solve this two-part conjecture. We also note that the well-known Mantel's theorem, which claims that every graph of order $n$ with size $m>\lfloor n/4\rfloor$ contains a triangle. Recently, Zhai and Shu (2022) obtained a spectral version of Mantel's theorem. In this paper, on the one hand, with the aid of Cioabă-Desai-Tait's novel method, we identify the graphs with the first two largest $A_\alpha$-indices among the $n$-vertex $C_4$-free graphs for $0<\alpha<1$ and $n\geq \frac{9}{\alpha^6}$. On the other hand, with the help of Zhai-Shu's eigenvector method, we identify the $C_4$-free graphs (other than the star) of size $m$ with no isolated vertex having the largest $A_\alpha$-index for $\frac{1}{2}\leq\alpha<1$ and $m\geq 3$. Our results improve some known ones of Tian, Chen, Cui (2021), Guo, Zhang (2022), Feng, Wei (2022) and Li, Qin (2021).