共查询到20条相似文献,搜索用时 484 毫秒
1.
白艳萍 《中北大学学报(自然科学版)》1996,(2)
在一个图G中,对于两个不相邻点u,v,用α(u,v)表示包含u和v的最大独立集的个数.本文证明了:如果G是一个包含n个顶点的3-连通图,对于G中每一对满足1≤|N(u)∩N(v)|≤α(u,v)-1的不相邻顶点u,v有max{d(u),d(v)}≥n+12,那么G是Hamiltonian连通的或者G属于特殊图类 相似文献
2.
王冬冬 《武汉工业学院学报》1997,(2)
证明了如下结果:设G是阶为n的2连通图,若对G中任一对距离为2的点u,v都有d(u)+d(v)≥n-1或|N(u)∪N(v)|≥n-δ,则G是Hamilton图,除非G属于一个特殊图类。δ=minv∈V(G){d(v)}称为最小度。 相似文献
3.
本文证明:如果一个n阶2-连通图G,对于其任意两个满足d(u,v)=2的相异顶点u,v,都有则G是点泛圈图。 相似文献
4.
关于2-连通图中最长圈的一个注记 总被引:2,自引:0,他引:2
卫兵 《中北大学学报(自然科学版)》1994,(4)
设G是一个n阶2-连通图,m>0是一个整数.本文证明了:如果对于图G中任意三点独立集S={u,v,w}},都存在x≠y∈S使得d(x)+d(y)≥m,则c(G)≥min{n,m}.其中c(G)表示图G的周长.这个结果推广了三个有关的已知结果。 相似文献
5.
孙惠泉 《北京邮电大学学报》1994,17(1):49
证明在v≥3的连通图G中,如果u与v为二不相邻接顶点,且d(u)+d(v)≥v-1,则G中有D圈当且仅当G+uv中有从D-圈.由此得到了D-圈存在性定理的一些推广. 相似文献
6.
孙惠泉 《北京邮电大学学报》1994,17(1):49-52
证明在ν≥3的连通图G中,如果u与v为二不相邻接顶点,且d(u)+d(v)≥ν-1,则G中有D-圈当且仅当G+uv中有D-圈,由此得到了D-圈存在性定理的一些推广。 相似文献
7.
梁立 《昆明理工大学学报(自然科学版)》1997,22(2):141-148
设G是连通图,XV(G),若G存在路P使得XV(P),则称G是X-可迹图;记NC2(X)=min{|N(u)∪N(v)|:u,v∈X且uvE(G)},我们得到如下结果:如果G是n阶2-连通图,XV(G)并且NC2(X)≥n-12,则G是X-可迹图,该结果在可迹图方面推广了B.J.Faudre等人在文献[4]中的结论 相似文献
8.
任韩 《武汉钢铁学院学报》1995,18(1):117-120
设G=(V,E)为n阶2-连通的1-坚韧图。将G的节点分类:g={v∈V|dG(v)≥n/2}而H={G\g}。如果H满足Ore-条件:A↓x,y∈V(H),(x,y)∈↑-E(H)→dH(x)+dH(y)≥|V(H)|,则有:(i)G是Hamilton的;(ii)若G不是偶图,则G至多丢失长为n-1的圈。 相似文献
9.
任韩 《武汉钢铁学院学报》1994,17(4):451-457
一个图G=(V,E)是[l,m]-泛连通的,如果在G的任意一对节点x与y之间有长为K-1的路PK(x,y),K=l,l+1,…,m。G具有性质P(K),如果对G的任何一对距离为2的节点x和y,有d(x)+d(y)≥K。作者探讨了一类P(K)的路连通性,改进了Faudree-Schelp定理,得到两个定理。定理1设G=(V,E)是n阶P(n-1)图。如果G是[n-1,n]-泛连通的,则G是[8,n] 相似文献
10.
泛圈性在NC下的进展 总被引:2,自引:1,他引:1
用领域并(NC)为工具对泛圈图进行探索性研究,获得的结果为:“2连通n(n≤3)阶图G,若NC≤2n/d,则G是泛圈图。”此结果大大地改进了图论专家R.F.Faudree、L.Lensiak及R.J.Gould和M.S.Jacob-son博士等人的结果:“2连通n(n≥19)阶图G,若GC≥(2n+5)/3,则G是泛圈图。 相似文献
11.
杨冬梅 《沈阳黄金学院学报》1996,15(3):288-291
主要结果是:若G为n阶3连通无爪图,δ=min{d(x)│x∈V(G)},δ^*=min{max(d(x),d(y))│x,y∈V(G),d(x,y)=2}≥1/2(n-δ+3),则G为Hamilton连通图。 相似文献
12.
k—覆盖图的一个充分条件 总被引:4,自引:4,他引:4
论证了整数n(n≥3)和k(k≥2),若k为奇数,则令k≥n-1,G是一个不含K1,n的2-边连通图,k│V(G)│≡o(mod2),设G的顶点最小度α(G)至少为(n^2/4(n-1)k+(3n-6)/2+(n-1)/4k,则G是k-覆盖图,并且说明了定理条件“2-边连通”不能减弱为“连通”。 相似文献
13.
14.
一个图G=(V,E)的一个k-全着色是从V∪E到Ik={1,2…k}上的一个映射ψ;如果对V∪E中任意两个相邻或相关联的元素e1,e2,都有ψ(e1)≠ψ(e2)时,则称ψ为G的一个正规全着色。图G的全色数定义为xT(G)=min{k|存在G的一个正规k-全着色}。令Cn为n个点的图,K↑-m为m个点的独立集,Δ为图的最大度。本文证明了在m≠n时联图Cm+Cn的全色数为Δ+1;在m+2〈n或m〉n 相似文献
15.
16.
论证了对整数n(n≥3)和k(k≥2),若k为奇数,则令k≥n-1,G是一个不含K1,n的2边连通图,k|V(G)|≡o(mod2),设G的顶点最小度α(G)至少为(n2/4(n-1))k+(3n-6)/2+(n-1)/4k,则G是k覆盖图.并且说明了定理中条件“2边连通”不能减弱为“连通”. 相似文献
17.
令G是一个有限群,S是G的一个生成元集,定义G上的Cayley图为Г=Г(GS),其中顶,久集为V(Г)=G,边集为E(Г)={(a,b)|a,b∈G,a(-1)b∈S},令Dn表示2n阶的二面体群,S=S(-1)是Dn的生成元集。本文证明了Dn上的Cayley图Г(Dn,S)具有Hamilton圈。从而证明了W.Holsztynski和R,F,E,Strube猜想[1]。 相似文献
18.
19.
刘玉柱 《沈阳建筑工程学院学报(自然科学版)》1995,(1)
设G是以(A,B)为顶点二分划的偶图,d(x)=min{d(u)|nA}=k≥2,λ=min{d(u)|uA\(x)}≥k,2≤|A|≤λ,|B|≤λ+k-2,则G的周长为2|A|. 相似文献
20.
本文把不相信两点的领集交与邻集并两个概念揉合在一起,以之刻划了比较广泛的一类哈密尔顿图、可迹图及哈密尔顿连通图,文中证明了:若s,t是两个整常数,t≥2,图G是阶为P的2连通图,对任何不相邻的顶点x与y,若它们邻集交以s为下界,邻集并以(sp-s)/(t+1)为下界,则G是哈密尔顿图,当把连通度和领集并的下界稍微减少或增大时,图G减弱为可迹图或加强为哈密尔顿连通图。 相似文献