報(bào)告題目：極小t-堅(jiān)韌圖
報(bào)告人：Gyula Y. Katona副教授
講座時(shí)間：6月6日（星期三）上午10:00-12:00
講座地點(diǎn)：理學(xué)院383會(huì)議室
邀請(qǐng)人：張勝貴教授、李斌龍副教授
報(bào)告簡(jiǎn)介：
一個(gè)圖G是極小t-堅(jiān)韌圖如果G的堅(jiān)韌度為t并且在G中刪去任意一條邊所得到的圖堅(jiān)韌度都變小。Kriesell猜想任意極小1-堅(jiān)韌圖的最小度是2。本報(bào)告提出并研究了Kriesell猜想的推廣形式：任意極小t-堅(jiān)韌圖的最小度是為[2t]。另一個(gè)有趣的結(jié)果是任意極小1-堅(jiān)韌無(wú)爪圖是圈。這引出這樣的問(wèn)題：一般的極小t-堅(jiān)韌圖占多大比例？在一些圖類(lèi)中極小t-堅(jiān)韌圖占多大比例？報(bào)告從不同角度考察了這些問(wèn)題。特別地，證明了對(duì)于任意有理數(shù)t，任意圖都是某個(gè)極小t-堅(jiān)韌圖的子圖。此外報(bào)告也考察了這一類(lèi)問(wèn)題的復(fù)雜性，證明判斷一個(gè)圖是否是極小t-堅(jiān)韌的這一問(wèn)題是DP-完全的（其中DP-問(wèn)題類(lèi)是NP-問(wèn)題類(lèi)與co-NP-問(wèn)題類(lèi)的交）。
報(bào)告人簡(jiǎn)介：
Gyula Y. Katona副教授博士畢業(yè)于匈牙利科學(xué)院，師從László Lovász和András Recski教授，自1999年起任職于布達(dá)佩斯技術(shù)與經(jīng)濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與信息論系，并于2011年擔(dān)任該系系主任。他曾獲匈牙利Bolyai Janos數(shù)學(xué)學(xué)會(huì)Rényi Kató獎(jiǎng)，與其它學(xué)者合著學(xué)術(shù)專(zhuān)著三部，發(fā)表論文50余篇。主要研究領(lǐng)域包括圖與超圖的哈密爾頓圈，圖的因子和堅(jiān)韌性，圖的Pebbling問(wèn)題等。
