Spanning trees in subcubic graphs

被引：0

作者：

Li, Rui ^{[1
]}

Cui, Qing ^{[2
]}

机构：

[1] Hohai Univ, Coll Sci, Dept Math, Nanjing 210098, Jiangsu, Peoples R China

[2] Nanjing Univ Aeronaut & Astronaut, Dept Math, Nanjing 210016, Peoples R China

来源：

ARS COMBINATORIA | 2014年 / 117卷

关键词：

Spanning tree; subcubic graphs; LEAVES;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every connected subcubic graph G has two spanning trees T-1, T-2 such that every component of G-E(T-1) is a path of length at most 3, and every component of G-E(T-2) is either a path of length at most 2 or a cycle.

引用

页码：411 / 415

页数：5

共 8 条

[1] Spanning trees with many leaves in graphs without diamonds and blossoms [J].

Bonsma, Paul ;

Zickfeld, Florian .

LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 :531-543

[2] Spanning trees with many leaves in graphs with minimum degree three [J].

Bonsma, Paul S. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (03) :920-937

[3] Connected domination and spanning trees with many leaves [J].

Caro, Y ;

West, DB ;

Yuster, R .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (02) :202-211

[4] SPANNING-TREES WITH MANY LEAVES IN CUBIC GRAPHS [J].

GRIGGS, JR ;

KLEITMAN, DJ ;

SHASTRI, A .

JOURNAL OF GRAPH THEORY, 1989, 13 (06) :669-695

[5] SPANNING-TREES IN GRAPHS OF MINIMUM DEGREE 4 OR 5 [J].

GRIGGS, JR ;

WU, MS .

DISCRETE MATHEMATICS, 1992, 104 (02) :167-183

[6] SPANNING-TREES WITH MANY LEAVES [J].

KLEITMAN, DJ ;

WEST, DB .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (01) :99-106

[7] NON-SEPARATING INDUCED CYCLES IN GRAPHS [J].

THOMASSEN, C ;

TOFT, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 31 (02) :199-224

[8] Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5 [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (01) :100-109

← 1 →