
Discrete Mathematics and Optimization Seminar

Mar. 14th, 2011
Hehui Wu
Longest Cycles in Graphs with Given Independence Number and Connectivity
University of Illinois at UrbanaChampaign

Abstract:
The ChvatalErdos 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 nvertex kconnected graph
with independence number a, and a >= k, then G has a cycle of length
at least k(n+ak)/a. We prove this conjecture. This is a
joint work with Suil O and Douglas B. West.



