The spectral radius of graphs without paths and cycles of specified length

DOI10.1016/J.LAA.2009.05.023zbMATH Open1217.05152arXiv0903.5351OpenAlexW2078483670MaRDI QIDQ962114FDOQ962114

Authors: Vladimir Nikiforov 

Publication date: 6 April 2010

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

Abstract: Let G be a graph with n vertices and mu(G) be the largest eigenvalue of the adjacency matrix of G. We study how large mu(G) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of natural open problems.

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

Recommendations

• On the spectral radii of graphs without given cycles
• Spectral conditions for the existence of specified paths and cycles in graphs
• The spectral radius of graphs with no odd wheels
• Spectral radius and Hamiltonicity of graphs
• Adjacency eigenvalues of graphs without short odd cycles

zbMATH Keywords

pathsspectral radiuscycles

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A sharp upper bound of the spectral radius of graphs
• Some Inequalities for the Largest Eigenvalue of a Graph
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• Bounds on graph eigenvalues. II
• Title not available (Why is that?)
• A spectral condition for odd cycles in graphs
• A bound on the spectral radius of graphs with \(e\) edges
• Degree powers in graphs with a forbidden even cycle
• Connected graphs without long paths
• Title not available (Why is that?)

Cited In (95)

• Spectral condition for Hamiltonicity of a graph
• Adjacency eigenvalues of graphs without short odd cycles
• The spectral radius of graphs with no odd wheels
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• The influence of Miroslav Fiedler on spectral graph theory
• The maximum spectral radius of wheel-free graphs
• Maxima of the \(Q\)-index: forbidden a Fan
• Spectral extremal graphs for intersecting cliques
• The maximum spectral radius of graphs without spanning linear forests
• The spectral radius of graphs with no intersecting odd cycles
• The signless Laplacian spectral radius of graphs with forbidding linear forests
• A Spectral Erdős-Sós Theorem
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• The spectral radius of graphs without long cycles
• Stability of Woodall's theorem and spectral conditions for large cycles
• Spectral conditions for the existence of specified paths and cycles in graphs
• The index of signed graphs with forbidden subgraphs
• On minimally 2-(edge)-connected graphs with extremal spectral radius
• A sufficient \(Q\)-spectral condition for a graph to be \(\beta\)-deficient involving minimum degree
• On the spectral moment of graphs with given clique number
• The spectral characterization of graphs of index less than 2 with no path as a component
• Sharp bounds for the signless Laplacian spectral radius in terms of clique number
• On the spectral radii of graphs without given cycles
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• The maximum spectral radius of graphs without friendship subgraphs
• Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• On a conjecture of spectral extremal problems
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• Generalized Turán problems for even cycles
• Maxima of the \(Q\)-index: forbidden even cycles
• A spectral condition for the existence of the square of a path
• A spectral condition for odd cycles in non-bipartite graphs
• The bipartite Turán number and spectral extremum for linear forests
• Ordering the maxima of \(L\)-index and \(Q\)-index: graphs with given size and diameter
• Spectral conditions for graphs to be \(k\)-Hamiltonian or \(k\)-path-coverable
• The maximum spectral radius of graphs of given size with forbidden subgraph
• A unique characterization of spectral extrema for friendship graphs
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The eigenvectors to the \(p\)-spectral radius of general hypergraphs
• The spectral Turán problem about graphs with no 6-cycle
• On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs
• Spectral radius and \(k\)-connectedness of a graph
• On the \(A_\alpha \)-spectral radius of graphs with given size
• Spectral extrema of graphs: forbidden hexagon
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• Maximum degree and minimum degree spectral radii of some graph operations
• On spectral radius of graphs with pendant paths
• Spectral radius, edge-disjoint cycles and cycles of the same length
• Spectral extremal results with forbidding linear forests
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and the 2-power of Hamilton cycle
• The spectral radius and \({\mathcal{P}}_{\ge \ell}\)-factors of graphs involving minimum degree
• Ordering \(Q\)-indices of graphs: given size and circumference
• Spectral extrema of 1-planar graphs
• The signless Laplacian spectral radius of \(2K_3\)-free graphs
• The spectral radius of graphs without trees of diameter at most four
• Spectral extremal graphs for edge blow-up of star forests
• Maxima of the \(Q\)-index of non-bipartite graphs: forbidden short odd cycles
• The \(Q\)-index and connectivity of graphs
• The minimum spectral radius for \(K_{r+1}\)-saturated graphs with \(r = 4\), 5
• Spectral extremal results on trees
• Maximum degree and spectral radius of graphs in terms of size
• The spectral even cycle problem
• On the spectral radius of graphs without a gem
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• On the spectral Turán problem of theta graphs
• Spectral extrema of graphs with bounded clique number and matching number
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Eigenvalues and cycles of consecutive lengths
• Maxima of the \(Q\)-index for \(3 K_3\)-free graphs
• The signless Laplacian spectral radius of graphs without intersecting odd cycles
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• Spectral extremal graphs without intersecting triangles as a minor
• Extremal results for \(C_3^-\)-free signed graphs
• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• Maxima of the \(Q\)-spectral radius of \(C_3 (C_4)\)-free graphs with given size and minimum degree \(\delta \geq 2\)
• Maximum spread of graphs and bipartite graphs
• Spectral Turán problems for intersecting even cycles
• The maximum number of \(P_\ell\) copies in \(P_k\)-free graphs
• Title not available (Why is that?)
• Spectral extremal problem on disjoint color-critical graphs
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• Maxima of the \(Q\)-index of non-bipartite \(C_3\)-free graphs
• The spectral radius of minor-free graphs
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
• Spectral extremal graphs for disjoint cliques
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• The spectral radius and \(k\)-power of Hamilton cycle of graphs
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Spectral radius of graphs of given size with forbidden subgraphs
• The unique spectral extremal graph for intersecting cliques or intersecting odd cycles

This page was built for publication: The spectral radius of graphs without paths and cycles of specified length

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