Domination in 3-tournaments

详细信息    查看全文

• 作者：D&aacute ; niel Kor&aacute ; ndi ^{daniel.korandi@math.ethz.ch" class="auth_mail" title="E-mail the corresponding author} ; Benny Sudakov¹ ; ^{benjamin.sudakov@math.ethz.ch" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Domination ; Generalized tournaments ; Girth ; Property SkSk
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：146
• 期：Complete
• 页码：165-168
• 全文大小：211 K

文摘

A 3-tournament is a complete 3-uniform hypergraph where each edge has a special vertex designated as its tail. A vertex set m>Xm> dominates m>Tm> if every vertex not in m>Xm> is contained in an edge whose tail is in m>Xm>. The domination number of m>Tm> is the minimum size of such an m>Xm>. Generalizing well-known results about usual (graph) tournaments, Gyárfás conjectured that there are 3-tournaments with arbitrarily large domination number, and that this is not the case if any four vertices induce two triples with the same tail. In this short note we solve both problems, proving the first conjecture and refuting the second.