๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On avoidable and unavoidable claws

โœ Scribed by Xiaoyun Lu; Da-Wei Wang; C.K. Wong

Book ID
104113987
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
316 KB
Volume
184
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A claw of degree k is a directed tree consisting of k paths emerging from a common root. We 19 prove that every claw of order n with degree less than ~n appears in every n-vertex tournament.

u Thus for large n, the maximum We also construct avoidable claws with degree approaching i3n. tl 2 such that every claw with degree An appears in every n-vertex tournament satisfies 2 ~< 23" This improves earlier bounds.

๐Ÿ“œ SIMILAR VOLUMES

On avoidable and unavoidable trees
On avoidable and unavoidable trees
โœ Xiaoyun Lu ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 574 KB

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.