2022/11/10 by Sarah Acquaviva, Acquaviva, Sarah, Deepak Bal +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.05726
openalex publication_date 2022/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≤ 10.