Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey (Q2277468): Difference between revisions

\textit{V. Chvátal} and \textit{P. Erdős} [Discrete Math. 2, 111-113 (1972; Zbl 0233.05123)] proved that a graph is hamiltonian if its independence number is not more than its connectivity, i.e., \(\alpha\leq k(\geq 2)\). The authors survey the extensive literature that has grown around this theorem during the past twenty years. Their survey, though restricted to results and conjectures that involve both independence number and connectivity, covers more than fifty such instances. These involve systems of disjoint paths, path coverings, cycle coverings, hamiltonicity, and pancyclicity in both graphs and digraphs.