Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs

Nikiforov [Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 179--189] showed that if $G$ is $K_{r+1}$-free then the spectral radius $ρ(G)\leq\sqrt{2m(1-1/r)}$, which implies that $G$ contains $C_3$ if $ρ(G)>\sqrt{m}$. In this paper, we follow this direction on determining which subgraphs will be contained in $G$ if $ρ(G)> f(m)$, where $f(m)\sim\sqrt{m}$ as $m\rightarrow \infty$. We first show that if $ρ(G)\geq \sqrt{m}$, then $G$ contains $K_{2,r+1}$ unless $G$ is a star; and $G$ contains either $C_3^+$ or $C_4^+$ unless $G$ is a complete bipartite graph, where $C_t^+$ denotes the graph obtained from $C_t$ and $C_3$ by identifying an edge. Secondly, we prove that if $ρ(G)\geq{\frac12+\sqrt{m-\frac34}}$, then $G$ contains pentagon and hexagon unless $G$ is a book; and if $ρ(G)>{\frac12(k-\frac12)+\sqrt{m+\frac14(k-\frac12)^2}}$, then $G$ contains $C_t$ for every $t\leq 2k+2$. In the end, some related conjectures are provided for further research.

No reviews yet.

No comments yet.