Independent sets, cliques and hamiltonian graphs (Q1900523): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:56, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent sets, cliques and hamiltonian graphs |
scientific article |
Statements
Independent sets, cliques and hamiltonian graphs (English)
0 references
8 April 1996
0 references
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\).
0 references
hamiltonian graphs
0 references
essential independent set
0 references