On spanning trees with high internal degree
classification
🧮 math.CO
keywords
degreeleastspanningconnectedeverygraphinternalminimum
read the original abstract
Alon and Wormald showed that any graph with minimum degree d contains a spanning star forest in which every connected component is of size at least \Omega((d/\log d)^{1/3}). They asked if any connected graph with minimum degree at least d has a spanning tree in which every internal vertex has degree at least cd/\log d, for some absolute constant c > 0. We give a simple example showing that this is not the case.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.