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

DOI10.1002/JGT.22899zbMATH Open1522.05050arXiv1905.09806MaRDI QIDQ6094048FDOQ6094048

Authors: Bruce Reed, Maya Stein 

Publication date: 9 October 2023

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

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.

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

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

zbMATH Keywords

minimum degreemaximum degreespanning tree

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• 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 probabilistic method. With an appendix on the life and work of Paul Erdős.
• On the Erdős–Sós conjecture for trees with bounded degree
• Spanning trees in dense graphs
• Degree conditions for embedding trees
• A Local Approach to the Erdös--Sós Conjecture
• Maximum and minimum degree conditions for embedding trees
• A variant of the Erdős-Sós conjecture

Cited In (6)

• Spanning trees without adjacent vertices of degree 2
• Title not available (Why is that?)
• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• A note on universal graphs for spanning trees
• Degree conditions for embedding trees
• Cycle intersection in spanning trees: a shorter proof of a conjecture and applications

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)