学 术 报 告

报告人: 高志成 教授
（加拿大Carleton大学数理统计系）
题目: Finding Long Cycles in 3-connected Graphs with Bounded Degrees

摘要: The problem of finding a long cycle in a general 3-connected graph is computationally very difficult. The problem becomes easier for 3-connected graphs with bounded degrees. In 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d 4 then G has a cycle of length $n^{log_{d-1} 2}$. In this talk we show that for d 100, G has a cycle of length $n^{log_{d} 2}$. Our proof uses Tutte decomposition of 2-connected graphs into 3-connected components, and it implies an algorithm of complexity $O(n^2)$ which finds a cycle of length at least $(1/2)n^{log_{d} 2}+2$.

地点: 闵行校区数学馆102室

时间: 2010年5月20日上午10:00-11:00