標題: 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-三月-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
顯示於類別:期刊論文


文件中的檔案:

  1. 000078782000002.pdf