Spanning trees without adjacent vertices of degree 2

Kasper Szabo Lyngsie*, Martin Merker

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

40 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 languageEnglish
Article number111604
JournalDiscrete Mathematics
Volume342
Issue number12
Number of pages11
ISSN0012-365X
DOIs
Publication statusPublished - 2019

Keywords

  • Spanning trees
  • Homeomorphically irreducible spanning
  • Trees
  • Non-separating cycles

Fingerprint Dive into the research topics of 'Spanning trees without adjacent vertices of degree 2'. Together they form a unique fingerprint.

Cite this