|
|||||
|
|
Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph |
|
| Authors: | Haruhide Matsuda Kenta Ozeki Tomoki Yamashita |
| Institution: | 1. Department of Mathematics, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama, 337-8570, Japan 2. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan 3. JST, ERATO, Kawarabayashi Large Graph Project, Tokyo, Japan 4. Department of Mathematics, Kinki University, 3-4-1 Kowakae, Higashiosaka, Osaka, 577-8502, Japan |
| Abstract: | Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |