An Asymptotically Tight Bound on the $Q$-index of Graphs with Forbidden Cycles

Vladimir Nikiforov

Publications de l'Institut Mathématique, _N_S_95 (2014) no. 109, p. 189 .

Résumé

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}ěeverline{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.

Détail

Classification : 15A42 05C50