Advances on two spectral conjectures regarding booksize of graphs

Abstract

The booksize $\mathrm{bk}(G)$ of a graph $G$, introduced by Erdős, refers to the maximum integer $r$ for which $G$ contains the book $B_r$ as a subgraph. This paper investigates two open problems in spectral graph theory related to the booksize of graphs. First, we prove that for any positive integer $r$ and any $B_{r+1}$-free graph $G$ with $m\ge (9r{)}^2$ edges, the spectral radius satisfies $\ddot{I}(G)\le \sqrt{m}$. Equality holds if and only if $G$ is a complete bipartite graph. This result improves the lower bound on the booksize of Nosal graphs (i.e., graphs with $\ddot{I}(G)>\sqrt{m}$) from the previously established $\mathrm{bk}(G)>\frac{1}{144}\sqrt{m}$ to $\mathrm{bk}(G)>\frac{1}{9}\sqrt{m}$, presenting a significant advancement in the booksize conjecture proposed Li, Liu, and Zhang. Second, we show that for any positive integer $r$ and any non-bipartite $B_{r+1}$-free graph $G$ with $m\ge (240r{)}^2$ edges, the spectral radius $\ddot{I}$ satisfies $\ddot{I}{}^2<m-1+\frac{2}{\ddot{I}-1}$, unless $G$ is isomorphic to $S_{m,s}^{+}$ for some $s\in \{1,\dots ,r\}$. This resolves Liu and Miao's conjecture and further reveals an interesting phenomenon: even with a weaker spectral condition, $\ddot{I}{}^2\ge m-1+\frac{2}{\ddot{I}-1}$, we can still derive the supersaturation of the booksize for non-bipartite graphs.

15 pages