The spectral radius of graphs without long cycles

Let Cℓ be a cycle of length ℓ and Sn,k=Kk∨Kn−k‾, the join graph of a complete graph of order k and an empty graph on n−k vertices, and Sn,k+ be the graph obtained from Sn,k by adding an edge in the independent set of Sn,k. Nikiforov conjectured that for a given integer k≥2, any graph G of sufficient...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2019-04, Vol.566, p.17-33
Main Authors: Gao, Jun, Hou, Xinmin
Format: Article
Language:English
Subjects:
Apexes
Cycle
Extremal problem
Graph theory
Linear algebra
Spectra
Spectral radius
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let Cℓ be a cycle of length ℓ and Sn,k=Kk∨Kn−k‾, the join graph of a complete graph of order k and an empty graph on n−k vertices, and Sn,k+ be the graph obtained from Sn,k by adding an edge in the independent set of Sn,k. Nikiforov conjectured that for a given integer k≥2, any graph G of sufficiently large order n with spectral radius μ(G)≥μ(Sn,k) (or μ(G)≥μ(Sn,k+)) contains C2k+1 or C2k+2 (or C2k+2), unless G=Sn,k (or G=Sn,k+). In this paper, a weaker version of Nikiforov's conjecture is considered, we prove that for a given integer k≥2, any graph G of sufficiently large order n with spectral radius μ(G)≥μ(Sn,k) (or μ(G)≥μ(Sn,k+)) contains a cycle Cℓ with ℓ≥2k+1 (or Cℓ with ℓ≥2k+2), unless G=Sn,k (or G=Sn,k+). These results also imply a result given by Nikiforov in (2010) [3, Theorem 2].
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2018.12.023