|
Discrete Mathematics and Optimization Seminar
|
Mar. 14th, 2011
Hehui Wu
Longest Cycles in Graphs with Given Independence Number and Connectivity
University of Illinois at Urbana-Champaign
|
Abstract:
The Chvatal--Erdos Theorem states that every graph whose connectivity
is at least its independence number has a spanning cycle. In 1976, Fouquet and
Jolivet conjectured an extension: If G is an n-vertex k-connected graph
with independence number a, and a >= k, then G has a cycle of length
at least k(n+a-k)/a. We prove this conjecture. This is a
joint work with Suil O and Douglas B. West.
|
|
|
|