𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


On unavoidable hypergraphs
✍ F. R. K. Chung; P. ErdΓΆs πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 518 KB
On q-trees
✍ Chong-Yun Chao; Nian-Zu Li; Shao-Ji Xu πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 301 KB

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

On zero-trees
✍ ZoltΓ‘n FΓΌredi; D. J. Kleitman πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 544 KB

## 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__.

Recursion on Homogeneous Trees
✍ Herman Ruge Jervell πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 201 KB