科研之友
微信
新浪微博
Facebook
分享链接
摘要
An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k + 1, one of the following condition holds: @@@ (i) there exist u not equal v epsilon S such that d(u) + d(v) >= n or vertical bar N(u) boolean AND N(v)vertical bar >= alpha(G); @@@ (ii) for any distinct u and v in S, vertical bar N(u) boolean OR N (v)vertical bar >= n - max{d(x) : x epsilon S}, @@@ then G is Hamiltonian. We prove that if for each essential independent set S of cardinality k + 1, one of conditions (i) or (ii) holds, then G is Hamiltonian. A number of known results on Hamiltonian graphs are corollaries of this result.
- 出版日期2010
- 单位海南热带海洋学院
