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

DOI10.1002/JGT.22897zbMATH Open1522.05049arXiv1905.09801MaRDI QIDQ6094046FDOQ6094046

Authors: Bruce Reed, Maya Stein 

Publication date: 9 October 2023

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

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.

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

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

zbMATH Keywords

minimum degreemaximum degreespanning tree

Mathematics Subject Classification ID

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

Cites Work

• The Erdös-Sós conjecture for graphs of girth 5
• Tree embeddings
• On maximal paths and circuits of graphs
• 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
• An approximate version of the Loebl-Komlós-Sós conjecture
• Title not available (Why is that?)
• 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 (7)

• Title not available (Why is that?)
• 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
• 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 I: An asymptotic result

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