论文标题
在随机的常规图中跨越树木的全能
Full Degree Spanning Trees in Random Regular Graphs
论文作者
论文摘要
我们研究了最大化图$ g $的$ t $ t $中全学位顶点的数量的问题；也就是说，$ t $学位的顶点数量等于$ g $。在立方图中，此问题等同于最大化$ t $中的叶子数量，并最大程度地减少连接的$ g $的统治组的大小。我们提供了一种算法，该算法（W.H.P.）在随机图表上运行时，该树具有至少$ 0.4591N $全度（以及叶子）的顶点。这提高了以前最著名的下限$ 0.4146 n $。我们还为$ r \ le 10 $的随机常规图$ g（n，r）$中的全学位顶点的数量提供了下限。
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$.
