EUVIMEDEUVIMED entdecken
Crossref

A Spectral Erdős-Sós Theorem

Sebastian Cioabă, Dheer Noal Desai, Michael Tait

SIAM Journal on Discrete Mathematics · 30.09.2023 · 37 (3) · 2228-2239

DOI: 10.1137/22m150650x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 26.09.2023. Verfasst von Sebastian Cioabă und 2 weiteren Autor:innen. Die Arbeit wurde bisher 26-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The famous Erdős–Sós conjecture states that every graph of average degree more than [Formula: see text] must contain every tree on [Formula: see text] vertices. In this paper, we study a spectral version of this conjecture. For [Formula: see text], let [Formula: see text] be the join of a clique on [Formula: see text] vertices with an independent set of [Formula: see text] vertices and denote by [Formula: see text] the graph obtained from [Formula: see text] by adding one edge. We show that for fixed [Formula: see text] and sufficiently large [Formula: see text], if a graph on [Formula: see text] vertices has adjacency spectral radius at least as large as [Formula: see text] and is not isomorphic to [Formula: see text], then it contains all trees on [Formula: see text] vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as [Formula: see text], then it either contains all trees on [Formula: see text] vertices or is isomorphic to [Formula: see text]. This answers a two-part conjecture of Nikiforov affirmatively.

Förderung

  • National Science Foundation

Zitieren

APA

Cioabă, S., Desai, D. N., & Tait, M. (2023). A Spectral Erdős-Sós Theorem. SIAM Journal on Discrete Mathematics, 37(3), 2228-2239. https://doi.org/10.1137/22m150650x

Vancouver

Cioabă S, Desai DN, Tait M. A Spectral Erdős-Sós Theorem. SIAM Journal on Discrete Mathematics. 2023;37(3):2228-2239. doi:10.1137/22m150650x

BibTeX
@article{Cioab2023,
  author = {Cioabă, Sebastian and Desai, Dheer Noal and Tait, Michael},
  title = {A Spectral Erdős-Sós Theorem},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2023},
  volume = {37},
  number = {3},
  pages = {2228--2239},
  doi = {10.1137/22m150650x}
}
Kostenlos starten →