z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom