A Spectral Erdős-Sós Theorem

DOI10.1137/22M150650XMaRDI QIDQ6072289zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba, Dheer Noal Sunil Desai, Michael Tait

Publication date 13 October 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spectral radiusErdős-Sós conjectureTurán-type problemBrualdi-Solheid problemspectral extremal

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Extremal problems in graph theory (05C35)

Abstract: The famous ErdH{o}s-S'os conjecture states that every graph of average degree more than $t-1$ must contain every tree on $t+1$ vertices. In this paper, we study a spectral version of this conjecture. For $n>k$, let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S_{n,k}^{+}$ the graph obtained from $S_{n,k}$ by adding one edge. We show that for fixed $kgeq2$ and sufficiently large $n$, if a graph on $n$ vertices has adjacency spectral radius at least as large as $S_{n,k}$ and is not isomorphic to $S_{n,k}$, then it contains all trees on $2k+2$ vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as $S_{n,k}^{+}$, then it either contains all trees on $2k+3$ vertices or is isomorphic to $S_{n,k}^{+}$. This answers a two-part conjecture of Nikiforov affirmatively.

Recommendations

• Spectral radius conditions for the existence of all subtrees of diameter at most four
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• On the Erdős-Sós conjecture for graphs on \(n=k+3\) vertices.
• On Erdős-Sós conjecture for trees of large size
• A Local Approach to the Erdös--Sós Conjecture

Cites work

• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3372065 (Why is no real title available?)
• A bound on the spectral radius of graphs with \(e\) edges
• A new upper bound for the spectral radius of graphs with girth at least 5
• A spectral condition for odd cycles in graphs
• Bounds on graph eigenvalues. II
• Eigenvalues of subgraphs of the cube
• On Erdős-Sós conjecture for trees of large size
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• On some extremal problems in graph theory
• On the Erdős-Sós conjecture for graphs on \(n=k+3\) vertices.
• On the Erd�s-S�s conjecture
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• On the spectral radii of graphs without given cycles
• On the spectral radius of graphs with a given domination number
• On the spectral radius of graphs with cut vertices
• On the structure of linear graphs
• Packing a tree with a graph of the same size
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extremal graphs for intersecting cliques
• Spectral radius and Hamiltonicity of graphs
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• The Erdös-Sós conjecture for graphs of girth 5
• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• The Erdős‐Sós Conjecture for trees of diameter four
• The history of degenerate (bipartite) extremal graph problems
• The maximum spectral radius of graphs without friendship subgraphs
• The spectral Turán problem about graphs with no 6-cycle
• The spectral radius of graphs on surfaces
• The spectral radius of graphs with no intersecting odd cycles
• The spectral radius of graphs with no odd wheels
• The spectral radius of graphs without paths and cycles of specified length
• The spectral radius of graphs without trees of diameter at most four
• Upper bounds on the spectral radius of book-free and/or \(K_{2,l}\)-free graphs

Cited in

(11)

• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• Spectral extremal results on trees
• scientific article; zbMATH DE number 1529473 (Why is no real title available?)
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• Spectral theory of extended Harper's model and a question by Erdős and Szekeres
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• A spectral Erdős-Rademacher theorem
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• A solution to a spectral poset problem of Lewis and Ohm

This page was built for publication: A Spectral Erdős-Sós Theorem

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