摘要
设Ｇ是连通图，ＸＶ（Ｇ），若Ｇ存在路Ｐ使得ＸＶ（Ｐ），则称Ｇ是Ｘ－可迹图；记ＮＣ２（Ｘ）＝ｍｉｎ｛｜Ｎ（ｕ）∪Ｎ（ｖ）｜：ｕ，ｖ∈Ｘ且ｕｖＥ（Ｇ）｝，我们得到如下结果：如果Ｇ是ｎ阶２－连通图，ＸＶ（Ｇ）并且ＮＣ２（Ｘ）≥ｎ－１２，则Ｇ是Ｘ－可迹图，该结果在可迹图方面推广了Ｂ．Ｊ．
Let G be a 2-connected graph, XV(G) . The graph G is X- traceable if G has a path P with XV(P) . We define NC 2(X) =min{|N(u)∪N(v)|: u,v∈X and uvE(G) }. In this paper,we obtain:If G is a 2-connected graph of order n,XV(G) and NC 2(X)≥n-12 , then G is X- traceable. This reault extends previous result of R.J.Faudreein X traceable graph.
出处
《昆明理工大学学报（理工版）》
CAS
1997年第2期141-148,共8页
Journal of Kunming University of Science and Technology(Natural Science Edition)
基金
云南省教委科研基金
关键词
邻域并
独立集
连通图
X-可迹图
可迹图
neighborhood unions
( X- )traceable graph
(X-) longest path
independent set
