Spanning trees without adjacent vertices of degree 2

被引：1
|
作者：
Lyngsie, Kasper Szabo [1 ]
Merker, Martin [1 ]
机构：
[1] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark
来源：
DISCRETE MATHEMATICS | 2019年 / 342卷 / 12期
关键词：
Spanning trees; Homeomorphically irreducible spanning trees; Non-separating cycles; GRAPHS;
D O I：
10.1016/j.disc.2019.111604
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页数：11
相关论文
共 50 条
12345