A Spectral Erdős-Sós Theorem

DOI10.1137/22M150650XzbMATH Open1522.05223arXiv2206.03339OpenAlexW4387045485MaRDI QIDQ6072289FDOQ6072289

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

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

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)