On the unavoidability of oriented trees

2018/12/12 by Dross, François, Havet, Frédéric · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1812.05167

Abstract

A digraph is \it n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is (n+k-1)-unavoidable. We then prove that every oriented tree of order n (n≥ 2) with k leaves is ((3)/(2)n+(3)/(2)k -2)-unavoidable and ((9)/(2)n -(5)/(2)k -(9)/(2))-unavoidable, and thus ((21)/(8) n- (47)/(16))-unavoidable. Finally, we prove that every oriented tree of order n with k leaves is (n+ 144k² - 280k + 124)-unavoidable.

Cited by

• Ramsey numbers of digraphs with local edge structure

Related

• Unavoidable trees in tournaments
• Blow-ups and extensions of trees in tournaments
• Oriented trees and paths in digraphs
• Oriented Trees in Digraphs without Oriented 4-cycles
• Unavoidable subgraphs in digraphs with large out-degrees