Spanning Trees: A Survey

被引：86

作者：

Ozeki, Kenta ^{[2
]}

Yamashita, Tomoki ^{[1
]}

机构：

[1] Kitasato Univ, Coll Liberal Arts & Sci, Minami Ku, Kanagawa 2520373, Japan

[2] Natl Inst Informat, Chiyoda Ku, Tokyo 1018430, Japan

来源：

GRAPHS AND COMBINATORICS | 2011年 / 27卷 / 01期

关键词：

Spanning trees; k-Trees; k-Ended trees; Branch vertices; k-Leaf connected; DEGREE-PRESERVING VERTICES; MINIMUM DEGREE CONDITION; NETWORK DESIGN PROBLEM; LINEAR-TIME ALGORITHM; MAXIMUM LEAF PROBLEMS; CUBIC GRAPHS; INDEPENDENT TREES; CIRCULANT GRAPHS; STEINER TREES; APPROXIMATION ALGORITHMS;

D O I：

10.1007/s00373-010-0973-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we give a survey of spanning trees. We mainly deal with spanning trees having some particular properties concerning a hamiltonian properties, for example, spanning trees with bounded degree, with bounded number of leaves, or with bounded number of branch vertices. Moreover, we also study spanning trees with some other properties, motivated from optimization aspects or application for some problems.

引用

页码：1 / 26

页数：26

共 50 条

[21] The number of spanning trees of a graph [J].

Kinkar C Das ;

Ahmet S Cevik ;

Ismail N Cangul .

Journal of Inequalities and Applications, 2013

[22] Spanning even trees of graphs [J].

Jackson, Bill ;

Yoshimoto, Kiyoshi .

JOURNAL OF GRAPH THEORY, 2024, 107 (01) :95-106

[23] The minimum labeling spanning trees [J].

Chang, RS ;

Leu, SJ .

INFORMATION PROCESSING LETTERS, 1997, 63 (05) :277-282

[24] The facets of the spanning trees polytope [J].

Chaourar, Brahim .

MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2022, 96 (01) :113-121

[25] Spanning trees on the Sierpinski gasket [J].

Chang, Shu-Chiuan ;

Chen, Lung-Chi ;

Yang, Wei-Shih .

JOURNAL OF STATISTICAL PHYSICS, 2007, 126 (03) :649-667

[26] Spanning trees and orientations of graphs [J].

Thomassen, Carsten .

JOURNAL OF COMBINATORICS, 2010, 1 (02) :101-111

[27] Spanning trees in random graphs [J].

Montgomery, Richard .

ADVANCES IN MATHEMATICS, 2019, 356

[28] The number of spanning trees of a graph [J].

Li, Jianxi ;

Shiu, Wai Chee ;

Chang, An .

APPLIED MATHEMATICS LETTERS, 2010, 23 (03) :286-290

[29] The number of spanning trees of a graph [J].

Das, Kinkar C. ;

Cevik, Ahmet S. ;

Cangul, Ismail N. .

JOURNAL OF INEQUALITIES AND APPLICATIONS, 2013,

[30] Constructing light spanning trees with small routing cost [J].

Wu, BY ;

Chao, KM ;

Tang, CY .

STACS'99 - 16TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1999, 1563 :334-344

← 1 2 3 4 5 →