caa a22 4500 475778146 CHVBK 20180406123636.0 cr unu---uuuuu 170329e20001201xx s 000 0 eng 10.1007/PL00007227 doi (NATIONALLICENCE)springer-10.1007/PL00007227 Rooted Spanning Trees in Tournaments [Elektronische Daten] [Xiaoyun Lu, Da-Wei Wang, Jiaofeng Pan, C. K. Wong] Abstract. : A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Springer-Verlag Tokyo, 2000 Lu Xiaoyun Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: xylu@cse.cuhk.edu.hk, CN aut Wang Da-Wei Institute of Information Science, Academia Sinica Taiwan e-mail: wdw@iis.sinica.edu.tw, TW aut Pan Jiaofeng Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: xylu@cse.cuhk.edu.hk, CN aut Wong C. K. Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: wongck@cse.cuhk.edu.hk, CN aut https://doi.org/10.1007/PL00007227 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00007227 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Lu Xiaoyun Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: xylu@cse.cuhk.edu.hk, CN aut NATIONALLICENCE 700 1- Wang Da-Wei Institute of Information Science, Academia Sinica Taiwan e-mail: wdw@iis.sinica.edu.tw, TW aut NATIONALLICENCE 700 1- Pan Jiaofeng Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: xylu@cse.cuhk.edu.hk, CN aut NATIONALLICENCE 700 1- Wong C. K. Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: wongck@cse.cuhk.edu.hk, CN aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer