On claws belonging to every tournament (Q1180417)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On claws belonging to every tournament |
scientific article |
Statements
On claws belonging to every tournament (English)
0 references
27 June 1992
0 references
A directed graph is said to be \(n\)-unavoidable if it is contained as a subgraph in every tournament on \(n\) vertices. Let \(L=(\ell_ 1,\ldots,\ell_ r)\) be a sequence of nonnegative numbers. A claw \(C(L)\) is a rooted directed tree obtained by identifying the roots of dipaths of sizes \(\ell_ 1+1,\ldots,\ell_ r+1\). A \(k\)- claw is a claw in which all \(\ell\)'s are \(k\), except possibly one of them that is less than \(k\). It is proved that there exist infinitely many \(n\) such that the 2-claw on \(n\) vertices is not unavoidable. This gives a negative answer to the conjecture of \textit{M. Saks} and \textit{V. Sós} [Coll. Math. Soc. Janos Bolyai 37, No. 2, 663-674 (1984; Zbl 0566.05032)]. On the other hand it is shown that any claw of rootdegree \(\leq n/4\) is unavoidable.
0 references
claws
0 references
tournament
0 references
rootdegree
0 references