The spectral radius of graphs without long cycles

DOI10.1016/J.LAA.2018.12.023MaRDI QIDQ1736228zbMATH OpenOpenAlexWikidataFDO

Authors Jun Gao, Xinmin Hou

Publication date 26 March 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04810

zbMATH Keywords

spectral radiuscycleextremal problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35)

Abstract: Nikiforov conjectured that for a given integer $kge2$, any graph $G$ of sufficiently large order $n$ with spectral radius $mu(G)geqmu(S_{n,k})$ (or $mu(G)gemu(S_{n,k}^{+}))$ contains $C_{2k+1}$ or $C_{2k+2}$(or $C_{2k+2}$), unless $G=S_{n,k}$ (or $G=S_{n,k}^{+})$, where $C_{e}ll$ is a cycle of length $ell$ and $S_{n,k}=K_{k}veeoverline{K}_{n-k}$, the join graph of a complete graph of order $k$ and an empty graph on $n-k$ vertices, and $S_{n,k}^{+}$ is the graph obtained from $S_{n,k}$ by adding an edge in the independent set of $S_{n,k}$. %This can be vie as spectral version of Erd"{o}s and S'{o}s conjecture. In this paper, a weaker version of Nikiforov's conjecture is considered, we prove that for a given integer $kge2$, any graph $G$ of sufficiently large order $n$ with spectral radius $mu(G)geqmu(S_{n,k})$ (or $mu(G)gemu(S_{n,k}^{+}))$ %$C_{2k+1}$ or $C_{2k+2}$(or $C_{2k+2}$), unless $G=S_{n,k}$ (or $G=S_{n,k}^{+})$$S_{n,k}$ ( or $S_{n,k}^{+}$) is the unique extremal graph with maximum radius among all of the graphs of order $n$ and contains a cycle $C_{ell}$ with $ellgeq2k+1$ (or $C_{ell}$ with $ellgeq2k+2$), unless $G=S_{n,k}$ (or $G=S_{n,k}^{+})$. These results also imply a result of Nikiforov given in [Theorem 2, The spectral radius of graphs without paths and cycles of specified length, LAA, 2010].

Recommendations

• Eigenvalues and cycles of consecutive lengths
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• The spectral radius of graphs without paths and cycles of specified length
• The spectral Turán problem about graphs with no 6-cycle

Cites work

• Connected graphs without long paths
• On maximal paths and circuits of graphs
• On the spectral radii of graphs without given cycles
• Some new results in extremal graph theory
• The spectral radius of graphs without paths and cycles of specified length

Cited in

(35)

• Spectral radius and the 2-power of Hamilton cycle
• The spectral radius and \({\mathcal{P}}_{\ge \ell}\)-factors of graphs involving minimum degree
• On the spectral radius of graphs without a gem
• Eigenvalues and cycles of consecutive lengths
• The sharp upper bounds on the \(A_{\alpha}\)-spectral radius of \(C_4\)-free graphs and Halin graphs
• The spectral radius of graphs without trees of diameter at most four
• Maximizing the degree powers of graphs with fixed size
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• The signless Laplacian spectral radius of \(2K_3\)-free graphs
• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• The spectral even cycle problem
• Maximizing the number of independent sets of fixed size in Kn‐covered graphs
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• Spectral extrema of graphs with bounded clique number and matching number
• Adjacency eigenvalues of graphs without short odd cycles
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• On the spectral radius of graphs without a star forest
• The maximum spectral radius of wheel-free graphs
• Proof and disproof of conjectures on spectral radii of coclique extension of cycles and paths
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• The spectral Turán problem about graphs with no 6-cycle
• The spectral radius and \(k\)-power of Hamilton cycle of graphs
• A unique characterization of spectral extrema for friendship graphs
• scientific article; zbMATH DE number 1833074 (Why is no real title available?)
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The maximum spectral radius of graphs without spanning linear forests
• Spectral extremal problem on disjoint color-critical graphs
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Signless Laplacian spectral radius of graphs without short cycles or long cycles
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• The unique spectral extremal graph for intersecting cliques or intersecting odd cycles
• A spectral condition for odd cycles in non-bipartite graphs
• Stability of Woodall's theorem and spectral conditions for large cycles
• Spectral radius, edge-disjoint cycles and cycles of the same length
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs

This page was built for publication: The spectral radius of graphs without long cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736228)