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

共 13 条

[1] Maximal trees with bounded maximum degree in a graph [J].

Aung, M ;

Kyaw, A .

GRAPHS AND COMBINATORICS, 1998, 14 (03) :209-221

[2] HAMILTONIAN PROPERTIES OF GRAPHS WITH LARGE NEIGHBORHOOD UNIONS [J].

BAUER, D ;

FAN, GH ;

VELDMAN, HJ .

DISCRETE MATHEMATICS, 1991, 96 (01) :33-49

[3] METHOD IN GRAPH THEORY [J].

BONDY, JA ;

CHVATAL, V .

DISCRETE MATHEMATICS, 1976, 15 (02) :111-135

[4]

Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9

[5] NEIGHBORHOOD UNIONS AND HAMILTONIAN PROPERTIES IN GRAPHS [J].

FAUDREE, RJ ;

GOULD, RJ ;

JACOBSON, MS ;

SCHELP, RH .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 47 (01) :1-9

[6] A NEW SUFFICIENT CONDITION FOR HAMILTONIAN GRAPHS [J].

FRAISSE, P .

JOURNAL OF GRAPH THEORY, 1986, 10 (03) :405-409

[7] Spanning spiders and light-splitting switches [J].

Gargano, L ;

Hammar, M ;

Hell, P ;

Stacho, L ;

Vaccaro, U .

DISCRETE MATHEMATICS, 2004, 285 (1-3) :83-95

[8] A sufficient condition for a graph to have a k-tree [J].

Kyaw, A .

GRAPHS AND COMBINATORICS, 2001, 17 (01) :113-121

[9]

LASVERGNAS M, 1971, CR ACAD SCI A MATH, V272, P1297

[10]

LIU Y, 1986, J CHANGSHA RAILWAY I, V4, P105

← 1 2 →