Back to Search Start Over

Trees with three leaves are (n+1)-unavoidable

Authors :
Frédéric Havet
S. Ceroi
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