On avoidable and unavoidable trees
β Scribed by Xiaoyun Lu
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 574 KB
- Volume
- 22
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
β¦ Synopsis
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. S6s ["On Unavoidable Subgraphs of Tournaments," Colloquia Mathematica Societatis Janos Bolyai 37, Finite and Infinite Sets, Egel; Hungary (1 981 1,663-6741 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 X(n) to be the largest real number such that every claw with degree d 5 X(n)n is n-unavoidable.
The example in X. Lu ["On Claws Belonging to Every Tournament," Combinatorica, Vol.
1 1 (1991 ), pp. 173-1 791 showed that X(n) < 1/2 for sufficiently large n, but the upper bound on X(n) given there tends to 1/2 for large n. Let X be the limsup of X(n) as n tends to infinity. In this paper we show that X is strictly less than 1/2, specifically X I 25/52.
π SIMILAR VOLUMES
We show that a graph G with n vertices is a q-tree if and only if its chromatic polynomial is P(G,A) = A(A -I)...(A -q + l ) ( As ) " -~ where n L q. The graphs which we consider here are finite, undirected, simple, and loopless. Let q be an integer L 1. The graphs called q-trees are defined by re
## Abstract Consider an integerβvalued function on the edgeβset of the complete graph K~m+1~. The weight of an edgeβsubset is defined to be the sum of the associated weights. It is proved that there exists a spanning tree with weight 0 modulo __m__.