Rooted Spanning Trees in Tournaments |
| |
| Authors: | Xiaoyun Lu Da-Wei Wang Jiaofeng Pan C. K. Wong |
| |
| Affiliation: | (1) Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: xylu@cse.cuhk.edu.hk, CN;(2) Institute of Information Science, Academia Sinica Taiwan e-mail: wdw@iis.sinica.edu.tw, TW;(3) Department of Computer Science and Engineering. The Chinese University of Hong Kong, Shatin, Hong Kong. e-mail: wongck@cse.cuhk.edu.hk, CN |
| |
| 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. Revised: November 9, 1998 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
