Document Type
Lecture
Publication Date
1-19-2012
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 . In this talk, we will introduce some results related to this conjecture and present some ideas on how we prove this conjecture. This is a joint work with Suil O and Douglas B. West.
Relational Format
presentation
Recommended Citation
Wu, Hehui, "Longest Cycles in Graphs with Given Independence Number and Connectivity" (2012). Combinatorics Seminar. 65.
https://egrove.olemiss.edu/math_combinatorics/65
COinS
