Back to Search
Start Over
Trees with three leaves are (n+1)-unavoidable
- Source :
- Discrete Applied Mathematics. 141:19-39
- Publication Year :
- 2004
- Publisher :
- Elsevier BV, 2004.
-
Abstract
- We prove that every tree of order n⩾5 with three leaves is (n+1)-unavoidable. More precisely, we prove that every tree A with three leaves of order n is contained in every tournament T of order n+1 except if (T;A) is (R5;S3+) or its dual, where R5 is the regular tournament on five vertices and S3+ is the outstar of degree three, i.e. the tree consisting of a root dominating three leaves. We then deduce that Sumner's conjecture is true for trees with four leaves, i.e. every tree of order n with four leaves is (2n−2)-unavoidable.
Details
- ISSN :
- 0166218X
- Volume :
- 141
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....e1d1c6b0823fc6686afb1f6dec571b23
- Full Text :
- https://doi.org/10.1016/s0166-218x(03)00366-4