Neighborhood unions and extremal spanning trees

被引：22

作者：

Flandrin, Evelyne ^{[1
]}

Kaiser, Tomas ^{[2
,3
]}

Kuzel, Roman ^{[2
,3
]}

Li, Hao ^{[1
,4
]}

Ryjacek, Zdenek ^{[2
,3
]}

机构：

[1] Univ Paris 11, CNRS, LRI,UMR8623, F-91405 Orsay, France

[2] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic

[3] Charles Univ Prague, Inst Theoret Comp Sci, CR-11636 Prague, Czech Republic

[4] Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Peoples R China

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 12期

关键词：

spanning spider; spanning tree; neighborhood union; Hamilton path; traceable graph;

D O I：

10.1016/j.disc.2007.04.071

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We generalize a known sufficient condition for the traceability of a graph to a condition for the existence of a spanning tree with a bounded number of leaves. Both of the conditions involve neighborhood unions. Further, we present two results on spanning spiders (trees with a single branching vertex). We pose a number of open questions concerning extremal spanning trees. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：2343 / 2350

页数：8