常用链接

ENG
宝马娱乐app下载
【学术讲座】布达佩斯技术与经济大学Gyula Y. Katona副教授报告通知
2018-06-06 08:46   国际合作处(国际教育学院) 审核人:   (点击: )

报告题目:极小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问题等。

关闭窗口
XML 地图 | Sitemap 地图