AN ASYMPTOTICALLY TIGHT BOUND ON THE $Q$-INDEX OF GRAPHS WITH FORBIDDEN CYCLES

摘要

Let $G$ be a graph of order $n$ and let $q(G)$ be the largest eigenvalue of the signless Laplacian of $G$. It is shown that if $kgeq2$, $n>5k^2$, and $q(G)geq n+2k-2$, then $G$ contains a cycle of length $l$ for each $lin{3,4,dots,2k+2}$. This bound on $q(G)$ is asymptotically tight, as the graph $K_{k}eeoverline{K}_{n-k}$ contains no cycles longer than $2k$ and q(K_{k}eeoverline{K}_{n-k})>n+2k-2-rac{2k(k-1)}{n+2k-3}. The main result gives an asymptotic solution to a recent conjecture about the maximum $q(G)$ of a graph $G$ with forbidden cycles. The proof of the main result and the tools used therein could serve as a guidance to the proof of the full conjecture.