Full degree spanning trees in random regular graphs

Sarah Acquaviva, Deepak Bal

Research output: Contribution to journalArticlepeer-review


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 that 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≤10.

Original languageEnglish
Pages (from-to)85-93
Number of pages9
JournalDiscrete Applied Mathematics
StatePublished - 15 Aug 2024


  • Algorithms
  • Differential equations method
  • Random regular graphs
  • Spanning trees


Dive into the research topics of 'Full degree spanning trees in random regular graphs'. Together they form a unique fingerprint.

Cite this