| Abstract: A vertex cut of a connected graph is a set of vertices whose removal renders the graph disconnected. The connectivity of a graph is the size of the smallest vertex cut. An independent set of a graph is a set of vertices such that between any two vertices in the set, there is no edge connecting them. The independence number is the size of the largest independent set. A cycle is spanning or Hamiltonian if it visits all the vertices. 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 joint work with Suil O and Douglas B. West. |