Premium
On k ‐ary spanning trees of tournaments
Author(s) -
Lu Xiaoyun,
Wang DaWei,
Chang Gerard J.,
Lin InJen,
Wong C. K.
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199903)30:3<167::aid-jgt2>3.0.co;2-o
Subject(s) - tournament , combinatorics , mathematics , spanning tree , hamiltonian path , unary operation , discrete mathematics , trémaux tree , path (computing) , graph , minimum spanning tree , kruskal's algorithm , computer science , pathwidth , line graph , programming language
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