Spanning trees without adjacent vertices of degree 2

Kasper Szabo Lyngsie; Martin Merker

doi:10.1016/j.disc.2019.111604

Spanning trees without adjacent vertices of degree 2

Kasper Szabo Lyngsie^*, Martin Merker

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

77 Downloads (Pure)

Abstract

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such that every graph of minimum degree at least d contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.

Original language	English
Article number	111604
Journal	Discrete Mathematics
Volume	342
Issue number	12
Number of pages	11
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2019.111604
Publication status	Published - 2019

Keywords

Spanning trees
Homeomorphically irreducible spanning
Trees
Non-separating cycles

Access to Document

10.1016/j.disc.2019.111604

FulltextAccepted author manuscript, 799 KBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{dba0948bdb6c47209e58ce432de08b34,

title = "Spanning trees without adjacent vertices of degree 2",

abstract = "Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such that every graph of minimum degree at least d contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.",

keywords = "Spanning trees, Homeomorphically irreducible spanning, Trees, Non-separating cycles",

author = "Lyngsie, {Kasper Szabo} and Martin Merker",

year = "2019",

doi = "10.1016/j.disc.2019.111604",

language = "English",

volume = "342",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "12",

}

TY - JOUR

T1 - Spanning trees without adjacent vertices of degree 2

AU - Lyngsie, Kasper Szabo

AU - Merker, Martin

PY - 2019

Y1 - 2019

N2 - Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such that every graph of minimum degree at least d contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.

AB - Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such that every graph of minimum degree at least d contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.

KW - Spanning trees

KW - Homeomorphically irreducible spanning

KW - Trees

KW - Non-separating cycles

U2 - 10.1016/j.disc.2019.111604

DO - 10.1016/j.disc.2019.111604

M3 - Journal article

SN - 0012-365X

VL - 342

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

M1 - 111604

ER -

Spanning trees without adjacent vertices of degree 2

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this