Premium
On avoidable and unavoidable trees
Author(s) -
Lu Xiaoyun
Publication year - 1996
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(199608)22:4<335::aid-jgt7>3.0.co;2-m
Subject(s) - tournament , combinatorics , mathematics , spanning tree , vertex (graph theory) , tree (set theory) , upper and lower bounds , degree (music) , order (exchange) , graph , discrete mathematics , mathematical analysis , physics , economics , finance , acoustics
A directed tree is a rooted tree if there is one vertex (the root) of in‐degree 0 and every other vertex has in‐degree 1. The depth of a rooted tree is the length of a longest path from the root. A directed graph G is called n ‐ unavoidable if every tournament of order n contains it as a subgraph. M. Saks and V. Sós [“On Unavoidable Subgraphs of Tournaments,” Colloquia Mathematica Societatis Janos Bolyai 37, Finite and Infinite Sets, Eger, Hungary (1981), 663–674] constructed unavoidable rooted spanning trees of depth 3. There they wrote, “It is natural to ask how small the depth of a spanning n ‐unavoidable rooted tree can be.” In this paper we construct unavoidable rooted spanning trees of depth 2. Note that the depth 2 is the best we can do. For each n define λ( n ) to be the largest real number such that every claw with degree d ≤ λ(n)n is n ‐unavoidable. The example in X. Lu [“On Claws Belonging to Every Tournament,” Combinatorica , Vol. 11 (1991), pp. 173–179] showed that λ(n) < 1/2 for sufficiently large n , but the upper bound on λ(n) given there tends to 1/2 for large n . Let λ be the lim sup of λ(n) as n tends to infinity. In this paper we show that λ is strictly less than 1/2, specifically λ ≤ 25/52. © 1996 John Wiley & Sons, Inc.