k-H-良好和(k+1)-HC-良好序列的一个充分条件  

A Sufficient Condition for k-H-Nice and(k+1)-HC-Nice Sequences

作　　者：刘一平[1] 田丰[1] 吴正声[1] 

机构地区：[1]南京师范大学数学系,中国科学院系统科学研究所

出　　处：《南京师大学报（自然科学版）》1994年第1期1-8,共8页Journal of Nanjing Normal University(Natural Science Edition)

摘　　要：本文改进了插点方法，证明了几个应用广泛的插点引理．在此基础上，利用极大圈的方法，统一证明了ｋ－Ｈ－良好序列和（ｋ＋１）－ＨＣ－良好序列的一个充分条件．所得到的定理改进、推广了许多关于Ｈａｍｉｌｌｏｎ图和Ｈａｍｉｌｌｏｎ连通图的已知结果．Let G be a simple finite graph, k+1(G) the set of independent sets of cardinality (k+1) of G. If Y∈k+l (G), denote si(Y) =|{v;|N(v)∩Y|=i}|(is∈{0,1, 2,…, k+1}). For k ≥ 2, a non-negative rational sequence η= (a1, a2,…, ak+1) is called k-H-nice ((k+1)-HC-nice), if for evely k-connected graph G ((k+1)-connected graph G*) for each Y impliesthat G is hamiltonian (G* is hamilton connected). By discussing the maximal cycles, we obtain some basic lcmmas which can be applied to both hamiltonian and hamilton connected problems.This idea enables us to prose the main result of this paper Ifη satisfics (i) a1≤1,(ii) for arbitrary i1, i2,…,ih ∈ {2, 3,…, k+1},implies then ηis k-H-nice and (k+1)-HC-nice. This result generalizesseveral sufficient conditions for graphs to be hamiltonian or hamilton connected.

关 键 词：K-H-良好 K-HC-良好 序列 极大圈 

分 类 号：O157.5[理学—数学]