报告题目：极小t-坚韧图

报告人：Gyula Y. Katona副教授

讲座时间：6月6日（星期三）上午10:00-12:00

讲座地点：理学院383会议室

邀请人：张胜贵教授、李斌龙副教授

报告简介：

一个图G是极小t-坚韧图如果G的坚韧度为t并且在G中删去任意一条边所得到的图坚韧度都变小。Kriesell猜想任意极小1-坚韧图的最小度是2。本报告提出并研究了Kriesell猜想的推广形式：任意极小t-坚韧图的最小度是为[2t]。另一个有趣的结果是任意极小1-坚韧无爪图是圈。这引出这样的问题：一般的极小t-坚韧图占多大比例？在一些图类中极小t-坚韧图占多大比例？报告从不同角度考察了这些问题。特别地，证明了对于任意有理数t，任意图都是某个极小t-坚韧图的子图。此外报告也考察了这一类问题的复杂性，证明判断一个图是否是极小t-坚韧的这一问题是DP-完全的（其中DP-问题类是NP-问题类与co-NP-问题类的交）。

报告人简介：

Gyula Y. Katona副教授博士毕业于匈牙利科学院，师从László Lovász和András Recski教授，自1999年起任职于布达佩斯技术与经济大学计算机科学与信息论系，并于2011年担任该系系主任。他曾获匈牙利Bolyai Janos数学学会Rényi Kató奖，与其它学者合著学术专著三部，发表论文50余篇。主要研究领域包括图与超图的哈密尔顿圈，图的因子和坚韧性，图的Pebbling问题等。