  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.4146 n$. We also provide lower bounds on the number of full degree vertices
in the random regular graph $G(n,r)$ for $r \le 10$.

Combinatorics