標題: | On k-ary spanning trees of tournaments |
作者: | Lu, XY Wang, DW Chang, GJ Lin, IJ Wong, CK 應用數學系 Department of Applied Mathematics |
關鍵字: | tournament;spanning tree;neighbor;Hamiltonian path;rooted tree;parent;child;depth;height |
公開日期: | 1-Mar-1999 |
摘要: | 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. |
URI: | http://hdl.handle.net/11536/31502 |
ISSN: | 0364-9024 |
期刊: | JOURNAL OF GRAPH THEORY |
Volume: | 30 |
Issue: | 3 |
起始頁: | 167 |
結束頁: | 176 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.