pith. sign in

arxiv: 1607.05460 · v1 · pith:VT4ZVZLJnew · submitted 2016-07-19 · 🧮 math.CO

On spanning trees with high internal degree

classification 🧮 math.CO
keywords degreeleastspanningconnectedeverygraphinternalminimum
0
0 comments X
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.