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

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

Authors Vladimir Nikiforov

Publication date 6 April 2010

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

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

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)

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.

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

Cites work

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

Cited in

(96)

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