Full degree spanning trees in random regular graphs

Sarah Acquaviva; Deepak Bal

doi:10.1016/j.dam.2024.04.010

Full degree spanning trees in random regular graphs

Sarah Acquaviva, Deepak Bal

Mathematics

Research output: Contribution to journal › Article › peer-review

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 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 language	English
Pages (from-to)	85-93
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	353
DOIs	https://doi.org/10.1016/j.dam.2024.04.010
State	Published - 15 Aug 2024

Keywords

Algorithms
Differential equations method
Random regular graphs
Spanning trees

Access to Document

10.1016/j.dam.2024.04.010

Cite this

@article{3938e03ac0af4ee7875b95ed53cadd07,

title = "Full degree spanning trees in random regular graphs",

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 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.",

keywords = "Algorithms, Differential equations method, Random regular graphs, Spanning trees",

author = "Sarah Acquaviva and Deepak Bal",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = aug,

day = "15",

doi = "10.1016/j.dam.2024.04.010",

language = "English",

volume = "353",

pages = "85--93",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Full degree spanning trees in random regular graphs

AU - Acquaviva, Sarah

AU - Bal, Deepak

PY - 2024/8/15

Y1 - 2024/8/15

N2 - 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.

AB - 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.

KW - Algorithms

KW - Differential equations method

KW - Random regular graphs

KW - Spanning trees

UR - http://www.scopus.com/inward/record.url?scp=85191302485&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2024.04.010

DO - 10.1016/j.dam.2024.04.010

M3 - Article

AN - SCOPUS:85191302485

SN - 0166-218X

VL - 353

SP - 85

EP - 93

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Full degree spanning trees in random regular graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this