Premium
Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
Author(s) -
Reed Bruce,
Stein Maya
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22899
Subject(s) - combinatorics , mathematics , vertex (graph theory) , conjecture , degree (music) , vertex connectivity , minimum degree spanning tree , graph , discrete mathematics , physics , acoustics
We prove that, ifm $m$ is sufficiently large, every graph onm + 1 $m+1$ vertices that has a universal vertex and minimum degree at least⌊2 m 3 ⌋$\lfloor \phantom{\rule[-0.5em]{}{0ex}}\frac{2m}{3}\rfloor $ contains each treeT $T$ withm $m$ edges as a subgraph. Our result confirms, for largem $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.