Spanning trees with a bounded number of leaves in a claw-free graph

被引：0

作者：

Kano, Mikio ^{[1
]}

Kyaw, Aung ^{[2
]}

Matsuda, Haruhide ^{[3
]}

Ozeki, Kenta ^{[4
]}

Saito, Akira ^{[5
]}

Yamashita, Tomoki ^{[6
]}

机构：

[1] Ibaraki Univ, Dept Comp & Informat Sci, Hitachi, Ibaraki 3168511, Japan

[2] E Yangon Univ, Dept Math, Yangon, Myanmar

[3] Shibaura Inst Technol, Dept Math, Minuma Ku, Saitama 3378570, Japan

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

[5] Nihon Univ, Dept Comp Sci & Syst Anal, Setagaya Ku, Tokyo 1568550, Japan

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

来源：

ARS COMBINATORIA | 2012年 / 103卷

关键词：

spanning tree; leaf; degree sum; claw-free graphs; HAMILTON CYCLES; PATHS;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a graph H and an integer k >= 2, let sigma(k)(H) denote the minimum degree sum of k independent vertices of H. We prove that if a connected claw-free graph G satisfies sigma(k+1)(G) >= vertical bar G vertical bar - k, then G has a spanning tree with at most k leaves. We also show that the bound vertical bar G vertical bar - k is sharp and discuss the maximum degree of the required spanning trees.

引用

页码：137 / 154

页数：18

共 50 条

[1] Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph
Haruhide Matsuda
Kenta Ozeki
Tomoki Yamashita
Graphs and Combinatorics, 2014, 30 : 429 - 437
[2] Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph
Matsuda, Haruhide
Ozeki, Kenta
Yamashita, Tomoki
GRAPHS AND COMBINATORICS, 2014, 30 (02) : 429 - 437
[3] SPANNING TREES OF A CLAW-FREE GRAPH WHOSE REDUCIBLE STEMS HAVE FEW LEAVES
Hoang, H. A. Pham
STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2023, 60 (01) : 2 - 15
[4] Spanning Trees with Few Leaves in Almost Claw-Free Graphs
Xiaodong CHEN
Mingchu LI
Meijin XU
JournalofMathematicalResearchwithApplications, 2016, 36 (04) : 450 - 456
[5] SPANNING k-ENDED TREES OF A CLAW-FREE GRAPH
Yan, Zheng
Tsugaki, Masao
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2016, 17 (04): : 453 - 459
[6] Spanning trees with few peripheral branch vertices in a connected claw-free graph
Hanh, D. D.
ACTA MATHEMATICA HUNGARICA, 2023, 169 (01) : 1 - 14
[7] Spanning trees with few peripheral branch vertices in a connected claw-free graph
D. D. Hanh
Acta Mathematica Hungarica, 2023, 169 : 1 - 14
[8] USING BOUNDED DEGREE SPANNING-TREES IN THE DESIGN OF EFFICIENT ALGORITHMS ON CLAW-FREE GRAPHS
CHROBAK, M
NAOR, J
NOVICK, MB
LECTURE NOTES IN COMPUTER SCIENCE, 1989, 382 : 147 - 162
[9] Two completely independent spanning trees of claw-free graphs
Chen, Xiaodong
Li, Mingchu
Xiong, Liming
DISCRETE MATHEMATICS, 2022, 345 (12)
[10] Spanning Trees With Leaves Bounded By Independence Number
Sun, Ling-li
APPLIED MATHEMATICS E-NOTES, 2007, 7 : 50 - 52

← 1 2 3 4 5 →