An Asymptotically Tight Bound on the $Q$-index of Graphs with Forbidden Cycles
Publications de l'Institut Mathématique, _N_S_95 (2014) no. 109, p. 189
Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts
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.
Classification :
15A42 05C50
@article{PIM_2014_N_S_95_109_a13,
author = {Vladimir Nikiforov},
title = {An {Asymptotically} {Tight} {Bound} on the $Q$-index of {Graphs} with {Forbidden} {Cycles}},
journal = {Publications de l'Institut Math\'ematique},
pages = {189 },
publisher = {mathdoc},
volume = {_N_S_95},
number = {109},
year = {2014},
language = {en},
url = {http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a13/}
}
TY - JOUR AU - Vladimir Nikiforov TI - An Asymptotically Tight Bound on the $Q$-index of Graphs with Forbidden Cycles JO - Publications de l'Institut Mathématique PY - 2014 SP - 189 VL - _N_S_95 IS - 109 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a13/ LA - en ID - PIM_2014_N_S_95_109_a13 ER -
%0 Journal Article %A Vladimir Nikiforov %T An Asymptotically Tight Bound on the $Q$-index of Graphs with Forbidden Cycles %J Publications de l'Institut Mathématique %D 2014 %P 189 %V _N_S_95 %N 109 %I mathdoc %U http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a13/ %G en %F PIM_2014_N_S_95_109_a13
Vladimir Nikiforov. An Asymptotically Tight Bound on the $Q$-index of Graphs with Forbidden Cycles. Publications de l'Institut Mathématique, _N_S_95 (2014) no. 109, p. 189 . http://geodesic.mathdoc.fr/item/PIM_2014_N_S_95_109_a13/