Independent sets, cliques and hamiltonian graphs (Q1900523): Difference between revisions

The author proves the following theorem: If \(G\) is a \(k\)-connected graph \((k \geq 2)\) on \(n\) vertices, \(V\) is a clique in \(G\) and if for every essential independent set \(S\) (i.e. there are two vertices in \(S\) having a common neighbor in \(G)\) having \(k + 1\) vertices the intersection of \(S\) and \(V\) is nonempty then \(G\) is hamiltonian, or \(G \backslash \{u\}\) is hamiltonian for some \(u \in V\), or \(G\) is in one of three classes of exceptional graphs. This theorem generalizes some results of Liu and Wei, Fan, Bondy, and Egawa and Saito. The proof breaks down into two stages. In the first stage the author proves that under the assumptions of the theorem having edges at certain places implies the absence of edges in other places (Lemmas 1, 2 and 3). In the second stage he uses the lemmas to show a number of claims leading to the results. These claims are globally proven as follows: first assume the contrary, then show that this invokes edges at some places, next use the lemmas to obtain non-edges in other places, and finally use these to construct large essential independent sets having empty intersection with \(V\).