Spanning tree with lower bound on the degrees

Zoltán Király

Published in:
Discrete Applied Mathematics, Volume 242, 2018, Pages 82-88. DOI link


We concentrate on some recent results of Egawa and Ozeki \cite{EO,EO2}, and He et al.\ \cite{He}. We give shorter proofs and polynomial algorithms as well.
We present two new proofs for the sufficient condition for having a spanning tree with prescribed lower bounds on the degrees, achieved recently by Egawa and Ozeki \cite{EO}. The first one is a natural proof using induction, and the second one is a simple reduction to the theorem of Lovász \cite{L}. Using an old algorithm of Frank \cite{F} we show that the condition of the theorem can be checked in time $O(m\sqrt{n})$, and moreover, in the same running time -- if the condition is satisfied -- we can also generate the spanning tree required. This gives the first polynomial algorithm for this problem.
Next we show a nice application of this theorem for the simplest case of the Weak Nine Dragon Tree Conjecture, and for the game coloring number of planar graphs, first discovered by He et al. \cite{He}.
Finally we give a shorter proof and a polynomial algorithm for a good characterization of having a spanning tree with prescribed degree lower bounds, for the special case when $G[S]$ is a cograph, where $S$ is the set of the vertices having degree lower bound prescription at least two. This theorem was proved by Egawa and Ozeki \cite{EO2} in 2014, they did not give a polynomial algorithm.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Spanning tree with lower bound on the degrees},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-04}

Last modification: 10.9.2021. Please email your comments to Tamás Király!