Independent sets,cliques and hamiltonian graphs |
| |
Authors: | Xin Liu |
| |
Institution: | (1) Institute of Applied Mathematics, Academia Sinica, 100080 Beijing, China |
| |
Abstract: | LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV
r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V
r , thenG is hamiltonian, orG {u} is hamiltonian for someu V
r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|