Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result

DOI10.1002/JGT.22899MaRDI QIDQ6094048zbMATH OpenFDO

Authors Bruce Reed, Maya Stein

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

minimum degreemaximum degreespanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Abstract: We prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $lfloorfrac2m3floor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$, an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves.

Recommendations

• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• On the Erdős-Sós conjecture and graphs with large minimum degree.
• Spanning trees in dense graphs
• Spanning trees with few leaves
• Spanning trees without adjacent vertices of degree 2

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 861349 (Why is no real title available?)
• scientific article; zbMATH DE number 881162 (Why is no real title available?)
• A Local Approach to the Erdös--Sós Conjecture
• A variant of the Erdős-Sós conjecture
• Degree conditions for embedding trees
• Maximum and minimum degree conditions for embedding trees
• On the Erdős–Sós conjecture for trees with bounded degree
• Spanning trees in dense graphs
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(6)

• Degree conditions for embedding trees
• Cycle intersection in spanning trees: a shorter proof of a conjecture and applications
• Spanning trees without adjacent vertices of degree 2
• scientific article; zbMATH DE number 1953079 (Why is no real title available?)
• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• A note on universal graphs for spanning trees

This page was built for publication: Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result

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