報告題目：極小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問題等。
