Independent sets, cliques and hamiltonian graphs (Q1900523): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Longest Cycles in 2-Connected Graphs with Prescribed Maximum Degree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on Hamiltonian circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New sufficient conditions for cycles in graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01793014 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2052598659 / rank | |||
Normal rank |
Latest revision as of 12:13, 30 July 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