Counting substructures and eigenvalues II: quadrilaterals

Abstract

Let $G$ be a graph and $\hat{I}»(G)$ be the spectral radius of $G$. A previous result due to Nikiforov [Linear Algebra Appl., 2009] in spectral graph theory asserted that every graph $G$ on $m\ge 10$ edges contains a 4-cycle if $\hat{I}»(G)>\sqrt{m}$. Define $f(m)$ to be the minimum number of copies of 4-cycles in such a graph. A consequence of a recent theorem due to Zhai et al. [European J. Combin., 2021] shows that $f(m)=\hat{I}\text{c◯}(m)$. In this article, by somewhat different techniques, we prove that $f(m)=\hat{I}˜(m^2)$. We left the solution to $\underset{m\to \infty }{\lim }\frac{f(m)}{m^2}$ as a problem, and also mention other ones for further study.

14 pages