共查询到20条相似文献,搜索用时 140 毫秒
1.
设G是一个图,B={v∈V(G)|不连通},如果B是独立集,并且v∈B,u∈V(G),使连通,则称G是几乎局部连通图。证明了连通、几乎局部连通K1,4-受限爪心独立图是完全圈可扩的。 相似文献
2.
文章讨论了无爪图的Hamilton连通性 ,给出邻集并与最大度的条件下Hamilton连通图的新的充分条件,证明了下述定理 :设G是一个3 -连通简单无爪图 ,连通度为k。如果对于G的每一个k阶独立集S满足 :对 u,v∈S,都有(1)k>3时,│N(u)∪N(v)│≥n-Δ(s) -k +2,(2)k=3时,│N(u)∪N(v)│≥n -Δ(s),则G是Hamilton连通的。 相似文献
3.
若爪心集D(G)是独立集,且任意 v∈V(G),〈N(v)〉是强2-控制的,则称G为拟无爪图.关于无爪图Hamilton性方面的很多结果已经被推广到了更大的图类一拟无爪图.得到了拟无爪图点泛圈性方面的一个结果。 相似文献
4.
半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。 相似文献
5.
证明了2-连通的爪心独立图G,如果对任意的非爪心点v,有d(v)≥k+l,对任意的爪心点u,存在v∈N(u),使得d(u)≥忌+2,那么G是模k点泛圈的. 相似文献
6.
石琳 《内蒙古大学学报(自然科学版)》1992,23(1):32-36
如果非平凡连通图G中任意的顶点v都对应G中唯一的顶点,使d(v,)=diam(G),则称G为平衡图.若平衡图G中由边uv∈B(G)可推出∈B(G),则称G为调和平衡图.本文证明了顶点数为n直径为d(d≥5)的调和平衡图G当G≌C_n时有关系式n≥3d. 相似文献
7.
王兵 《山东大学学报(理学版)》2007,42(10):111-113
讨论了比无爪图更广泛的图——拟无爪图,得到了以下两个结果:
(ⅰ) 若图G是拟无爪图,且满足ω(G-S)≤t(G), 则2t(G)=κ(G).
(ⅱ) 若图G是拟无爪图,对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3), 则γ(G)=i(G),该结果是最好可能的.
以上结果扩展了无爪图的相应结果. 相似文献
8.
9.
伊磊 《伊犁师范学院学报(自然科学版)》2010,(3)
本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限. 相似文献
10.
通过连通图的研究给出μ-临界m-连通m-正则图的一种构造方法。并给出关于μ-临界图的结论:G是4-连通(p,q)图,P≥9,如果存在线x=uv及S包含于V(G)使G-x-S有两个支A,B,u∈A,v∈B,则当|A| ≥3或|B|≥3时,G不是μ-临界图。 相似文献
11.
王兵 《曲阜师范大学学报》2003,29(3):41-43
给出了弱局部连通的定义,证明了顶点数不少于3的连通图、弱局部连通图、Kl,p-约束图是完全圈可扩的,改进了朱永津、王江鲁(1998)文中关于蜀Kl,p-约束图的完全圈可扩性的相应结果。 相似文献
12.
图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法. 相似文献
13.
14.
邓汉元 《北京理工大学学报》1989,(1)
Chia G L在1986年提出了这样1个问题:所有连通点可迁图是否是色唯一的?本文给出了一族连通点可迁图,它们都不是色唯一的,否定地回答了这个问题。 相似文献
15.
王兵 《内蒙古师范大学学报(自然科学版)》2003,32(3):216-219
借助于新的连通性——几乎局部连通的定义,证明了连通、几乎局部连通、强K1.p-约束图的完全圈可扩。这一结果涵盖了拟无爪图上的相应结果。 相似文献
16.
柳柏濂 《华南师范大学学报(自然科学版)》1985,(1):1
本文证明了关于连通图划分的一个定理.运用这个定理,简化了标号连通图和标号树的递归计数关系的证明,并导出了给定价数和根点块数的有根标号连通图和二色标号连通图的递归计数式. 相似文献
17.
18.
如果图G中任意1个顶点的导出子图中至少含有t条边,则称G为[s,t]-图.笔者证明:如果G是连通、局部连通[4,1]-图,则G是完全圈可扩的或者G属于图类F(Kn11,Kn2,Kn3,K2). 相似文献
19.
证明如下结论:设G是连通、N2-局部连通、δ≥6的K1,4-受限图,如果G中不含有同构于G1,G2或G3的导出子图H。则G含哈密顿圈. 相似文献
20.
杨维奇 《北京理工大学学报》1987,(4)
本文的主要目的是研究多连通区域的一个新的不变量,并把它定义为区域的模。当n=2时,我们所定义的模与通常的模一致。我们讨论了这种模的一些性质及应用。 相似文献