Extensions and consequences of Chvátal-Erdös' theorem (Q1923778): Difference between revisions

A well-known result of Chvátal and Erdös states that if \(G\) is a graph with at least 3 vertices such that \(\alpha(G)\leq \kappa(G)\), then \(G\) is hamiltonian. An ascending chain of generalizations of this result is given terminating with the following result. If \(G\) is a connected graph on at least 3 vertices such that for every connected subgraph \(H\) of \(G\) with \(N_2(H)\neq\varnothing\) (where \(N_2(H)\) is the set of vertices at a distance 2 from \(H\)) there does not exist an independent set \(S\) in \(N_2(H)\) and a matching \(M\) in \(G\) with \(|S|=|M|=|N(H)|\) and such that \(V(M)=S\cup N(H)\), then \(G\) is hamiltonian. Other well-known hamiltonian results, for example the theorem of Ore, are consequences of this generalization.