Premium
On the Thomassen's conjecture *
Author(s) -
Li Jianping
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.1011
Subject(s) - conjecture , mathematics , combinatorics , graph , discrete mathematics
C. Thomassen proposed a conjecture: Let G be a k ‐connected graph with the stability number α ≥ k , then G has a cycle C containing k independent vertices and all their neighbors. In this paper, we will obtain the following result: Let G be a k ‐connected graph with stability number α = k + 3 and C any longest cycle of G , then C contains k independent vertices and all their neighbors. This solves Thomassen's conjecture for the case α = k + 3. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 168–180, 2001