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

Vladimir Nikiforov

Abstract: 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 $k\geq2$, $n>5k^2$, and $q(G)\geq n+2k-2$, then $G$ contains a cycle of length $l$ for each $l\in\{3,4,\dots,2k+2\}$. This bound on $q(G)$ is asymptotically tight, as the graph $K_{k}\vee\overline{K}_{n-k}$ contains no cycles longer than $2k$ and
q(K_{k}\vee\overline{K}_{n-k})>n+2k-2-\frac{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.

Classification (MSC2000): 15A42; 05C50

Full text of the article: (for faster download, first choose a mirror)

• Compressed DVI file (24 kilobytes)
• Compressed PostScript file (412 kilobytes)
• PDF file (160 kilobytes)