主题：二部竞赛图和多部竞赛图中的圈结构：Hamilton圈、泛圈性和圈可扩性
时间：2020年4月28日（星期二） 14:30-16:30
地点：腾讯会议会议室
会议链接：https://meeting.tencent.com/s/50IHEtme1ab6
会议号：871455290
报告人：张赞波
内容纲要：图的圈结构是图论的重要研究课题。其中，图的Hamilton圈，即经过每个顶点恰好一次的圈，因其与旅行售货商问题等著名计算问题相关而广受图论和计算机学科关注。图中具有Hamilton圈的性质称为Hamilton性。图论中对Hamilton圈的关注点之一为其存在性的充分条件：即寻找图的性质P，使得所有满足性质P的图G都包含有Hamilton圈。1972年，Bondy教授指出，几乎所有这样导致G有Hamilton圈的性质P，也能同时导致G有所有其他长度的圈——这种性质定义为泛圈性。1989年Hendry进一步加强了泛圈性，定义了圈可扩性。给定图G，如果对于G中每一个非Hamilton圈C，都有另一个圈C',使得C'的顶点集合是由C的顶点集合添加一个顶点而得到，则C是圈可扩的。圈可扩性和泛圈性具有重要的理论意义，同时也因其与网络设计相关而在网络科学中受到不少关注。本报告讨论重要的有向图类——二部竞赛图和多部竞赛图的Hamilton性、泛圈性和圈可扩性。其中，我们得到一个重要的结果是，在二部竞赛图中，排除一个可以刻画的例外图类，Hamilton性、泛圈性和圈可扩性是等价的。