Name
Abstract | ||
|---|---|---|
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 ≥ 4. © 1999 John & Sons, Inc. J Graph Theory 30: 167–176, 1999 Part of this work was done while visiting the Chinese University of Hong Kong. Research by Dr. Gerard J. Chang supported in part by the National Science Council under grant NSC87-2115-M009-007. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1002/(SICI)1097-0118(199903)30:3<>1.0.CO;2-C | Journal of Graph Theory |
Keywords | Field | DocType |
hong kong,fixed positive integer k,general problem,dr. gerard j. chang,inc. j graph theory,national science council,chinese university,hamiltonian path,minimum number h,spanning tree,tournament,depth,height | Graph theory,Integer,Discrete mathematics,Combinatorics,Tournament,Minimum degree spanning tree,Hamiltonian path,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
30 | 3 | 0364-9024 |
Citations | PageRank | References |
1 | 0.35 | 3 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaoyun Lu | 1 | 1 | 0.35 |
| Da-Wei Wang | 2 | 277 | 28.60 |
| Gerard J. Chang | 3 | 1163 | 112.81 |
| In-Jen Lin | 4 | 55 | 4.69 |
| C. K. Wong | 5 | 1459 | 513.44 |