The high order spectral radius of graphs without long cycles or paths

2025/10/06 by Yuntian Wang, Lizhu Sun, Wang, Yuntian +3 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory in Mathematical Physics

paper · pdf · doi:10.48550/arxiv.2510.04461

Abstract

In 1959, Erdős and Gallai established two classic theorems, which determine the maximum number of edges in an n-vertex graph with no cycles of length at least k, and in an n-vertex graph with no paths on k vertices, respectively. Subsequently, generalized and spectral versions of the Erdős-Gallai theorems have been investigated. A concept of a high order spectral radius for graphs was introduced in 2023, defined as the spectral radius of a tensor and termed the t-clique spectral radius ρ_t(G). In this paper, we establish a high order spectral version of Erdős-Gallai theorems by employing the t-clique spectral radius, i.e., we determine the extremal graphs that attain the maximum t-clique spectral radius in the n-vertex graphs with no cycles of length at least k and in the n-vertex graphs with no paths on k vertices, respectively.

Citations

• Spectral extremal problems for non-bipartite graphs without odd cycles
• A tensor's spectral bound on the clique number
• Generalized Turán problems for a matching and long cycles
• The high order spectral extremal results for graphs and their applications
• Generalized Turán problem for a path and a clique
• An Erdős-Stone type result for high-order spectra of graphs
• On a generalization of the spectral Mantel's theorem
• The spectral even cycle problem
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Eigenvalues and cycles of consecutive lengths
• Adjacency eigenvalues of graphs without short odd cycles
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• The spectral radius of graphs without long cycles
• The maximum number of cliques in graphs without long cycles
• On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs
• Spectral conditions for the existence of specified paths and cycles in graphs
• Symmetric Nonnegative Tensors and Copositive Tensors
• Perron–Frobenius theorem for nonnegative multilinear forms and extensions
• The spectral radius of graphs without paths and cycles of specified length

Cited by

• The k-core of a graph and its high-order spectra

Related

• A (forgotten) upper bound for the spectral radius of a graph
• On a generalization of the spectral Mantel's theorem
• The spectral radius of graphs without paths and cycles of specified length
• Extremal problems for the p-spectral radius of graphs
• The maximum spectral radius of wheel-free graphs