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

DOI10.1016/J.LAA.2009.05.023MaRDI QIDQ962114zbMATH OpenOpenAlexFDO

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

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)