Full Degree Spanning Trees in Random Regular Graphs

DOI10.1016/J.DAM.2024.04.010MaRDI QIDQ6416835zbMATH OpenFDO

Authors Sarah Acquaviva, Deepak Bal

Publication date 10 November 2022

Full work available at URL https://doi.org/10.1016/J.DAM.2024.04.010

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

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 $rle10$.

Recommendations

• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning trees with many leaves in cubic graphs
• The number of bounded‐degree spanning trees
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

This page was built for publication: Full Degree Spanning Trees in Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416835)