Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result

DOI10.1002/JGT.22897MaRDI QIDQ6094046zbMATH 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.09801

zbMATH Keywords

minimum degreemaximum degreespanning tree

Mathematics Subject Classification ID

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

Abstract: In this paper and a companion paper, 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 recent conjecture by Havet, Reed, Stein, and Wood. The present paper already contains an approximate version of the result.

Recommendations

• Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Universality for bounded degree spanning trees in randomly perturbed graphs
• The asymptotic number of spanning trees in circulant graphs (extended abstract)
• The scaling limit of the minimum spanning tree of the complete graph
• On the Minimum Number of Spanning Trees ink-Edge-Connected Graphs
• Lower and upper bounds for the spanning tree with minimum branch vertices
• On the asymptotic behavior of the maximum number of spanning trees in circulant graphs
• The asymptotic number of spanning trees in circulant graphs

Cites work

• scientific article; zbMATH DE number 2086426 (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
• An approximate version of the Loebl-Komlós-Sós conjecture
• Degree conditions for embedding trees
• Maximum and minimum degree conditions for embedding trees
• On maximal paths and circuits of graphs
• On the Erdős–Sós conjecture for trees with bounded degree
• Spanning trees in dense graphs
• The Erdös-Sós conjecture for graphs of girth 5
• 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
• Tree embeddings

Cited in

(7)

• Cycle intersection in spanning trees: a shorter proof of a conjecture and applications
• scientific article; zbMATH DE number 1953079 (Why is no real title available?)
• Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
• Transversal factors and spanning trees
• High degree graphs contain large-star factors
• Trees through specified vertices
• 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 I: An asymptotic result

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