Full Degree Spanning Trees in Random Regular Graphs

Abstract

We study the problem of maximizing the number of full degree vertices in a spanning tree $T$ of a graph $G$; that is, the number of vertices whose degree in $T$ equals its degree in $G$. In cubic graphs, this problem is equivalent to maximizing the number of leaves in $T$ and minimizing the size of a connected dominating set of $G$. We provide an algorithm which produces (w.h.p.) a tree with at least $0.4591n$ vertices of full degree (and also, leaves) when run on a random cubic graph. This improves the previously best known lower bound of $0.4146n$. We also provide lower bounds on the number of full degree vertices in the random regular graph $G(n,r)$ for $r\le 10$.

10 pages, 3 figures