EMIS ELibM Electronic Journals Publications de l'Institut Mathématique, Nouvelle Série
Vol. 95[109], pp. 189–199 (2014)

Previous Article

Next Article

Contents of this Issue

Other Issues


ELibM Journals

ELibM Home

EMIS Home


Pick a mirror

 

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

Vladimir Nikiforov

Department of Mathematical Sciences, University of Memphis, Memphis, USA

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)


Electronic fulltext finalized on: 31 Mar 2014. This page was last modified: 2 Apr 2014.

© 2014 Mathematical Institute of the Serbian Academy of Science and Arts
© 2014 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition