报告题目：Making a tournament k-strong
报 告 人：Anders Yeo（南丹麦大学 教授）
报告时间：2022年5月25日 下午15:00开始
报告地点：腾讯会议线上报告
会议链接：//meeting.tencent.com/dm/l99r1LIZulHD
会议ID： 844-526-994
报告摘要：A digraph is k-strong if it has n ≥ k+1 vertices and every induced subdigraph on at least n−k+1 vertices is strongly connected. A tournament is a digraph with no pair of non-adjacent vertices. We prove that every tournament on n ≥ k+1 vertices can be made k-strong by adding no more than k(k+1)/2 arcs. This solves a conjecture from 1994. A digraph is semicomplete if there is at least one arc between any pair of distinct vertices x, y. Since every semicomplete digraph contains a spanning tournament, the result above also holds for semicomplete digraphs. Our result also implies that every semicomplete digraph on at least 3k−1 vertices can be made k-strong by reversing no more than k(k+1)/2 arcs.
报告人简介：Anders Yeo，南丹麦大学(University of Southern Denmark)数学与计算机系教授。博士毕业于丹麦奥登塞大学(Odense University)，师从J. Bang-Jensen教授与G. Gutin教授。主要研究领域为图论、组合优化、算法与计算复杂性。担任Discrete Mathematics and Theoretical Computer Science期刊编委。在Springer出版社出版学术著作2部；在Journal of Combinatorial Theory, Series B、Combinatorica、Journal of Graph Theory、SIAM Journal on Discrete Mathematics、Combinatorics, Probability and Computing、European Journal of Combinatorics、Algorithmica等图论组合、理论计算机科学领域的主流期刊上发表学术论文190多篇。
