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

Abstract

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 $\ddot{I}(G)\le \sqrt{2m(1-1/r)}$, which implies that $G$ contains $C_3$ if $\ddot{I}(G)>\sqrt{m}$. In this paper, we follow this direction on determining which subgraphs will be contained in $G$ if $\ddot{I}(G)>f(m)$, where $f(m)\sim \sqrt{m}$ as $m\to \infty$. We first show that if $\ddot{I}(G)\ge \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 $\ddot{I}(G)\ge \frac{1}{2}+\sqrt{m-\frac{3}{4}}$, then $G$ contains pentagon and hexagon unless $G$ is a book; and if $\ddot{I}(G)>\frac{1}{2}(k-\frac{1}{2})+\sqrt{m+\frac{1}{4}(k-\frac{1}{2}{)}^2}$, then $G$ contains $C_t$ for every $t\le 2k+2$. In the end, some related conjectures are provided for further research.

21 pages, 6 pages. This paper has been accepted for publication in European Journal of Combinatorics