On k-ary spanning trees of tournaments
檔案
- 000078782000002.pdf (114.4 KB, Adobe PDF)
日期
1999-03-01
類型
系所
期刊名稱
JOURNAL OF GRAPH THEORY
卷期與頁次
第 30 卷第 3 期,頁 167–176
ISSN
0364-9024
語言
英文
摘要
It is well known that every tournament contains a Hamiltonian path, which can be restated as that every tournament contains a unary spanning tree. The purpose of this article is to study the general problem of whether a tournament contains a k-ary spanning tree. In particular, we prove that, for any fixed positive integer k, there exists a minimum number h(k) such that every tournament of order at least h(k) contains a k-ary spanning tree. The existence of a Hamiltonian path for any tournament is the same as h(1) = 1. We then show that h(2) = 4 and h(3) = 8. The values of h(k) remain unknown for k greater than or equal to 4. (C) 1999 John Wiley & Sons. Inc. J Graph Theory 30: 167-176, 1999.