首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 156 毫秒
1.
不含孤立点的图G称为全控制边临界的,如果对任意两个不相邻顶点u和v, 有γt(G uv)<γt(G).也称这样的图为γt-临界的. 如果该图G的全控制数为k,称G为k-γt-临界的.一个γt-临界图G称为强γt-临界的, 如果对任意顶点v∈V(G)存在G的一个基数为γt(G)-1的控制集D使得G[D]除v外不含孤立点.研究了强γt-临界图的性质,给出了一个由小的强γt-临界图构造大强γt-临界图的方法.  相似文献   

2.
文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥6且ξ4(G)≤3n(G)/2+3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥6且对图中每个三角形T至少存在一个顶点v∈V(T)...  相似文献   

3.
文章给出了满足一定条件的图的λ6-最优性的领域交条件.设图G是连通图,若对G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥10且|X5|≤5,则G是λ6-最优的;若对于连通图G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥10且对图中每个三角形T至少存在一个顶点v∈V(T)使得d(v)≥v2+5,则G是λ6-最优的.  相似文献   

4.
文章给出了二部图是λ4-最优的一个领域交条件.设n为一个不小于8的正整数,令G=(X∪Y,E)为一个n阶二部图且ξ4(G)≤n/2.若G有一个饱和X或Y中所有顶点的匹配且对任意的u,v∈X和u,v∈Y都有|N(u)∩N(v)|≥4,则G是λ4-最优的.  相似文献   

5.
图G的一个L(2,1)-标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)|≥1;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为.那么,图G的L(1,1)-标号数λ(G)是是G的所有L(1,1)-标号下的跨度max{f(v);v∈V(G)}的最小数.完全确定了点接拟梯子的L(1,1)-标号数.  相似文献   

6.
一个图G的L(2,1,1)-标号是指从顶点集V(G)到非负整数集的一个映射f,且使得:当d(u,v)=1时,|f(u)-f(v)|≥2;当d(u,v)=2或3时,|f(u)-f(v)|≥1.不妨假设设最小的标号为0.则,G的L(2,1,1)-标号数λ(G)是G的所有L(2,1,1)-标号下的跨度max{f(v);v∈V(G)}的最小值.完全确定了点接拟梯子的L(2,1,1)-标号数.  相似文献   

7.
图G的L(2,1)-标号是从顶点集V(G)到非负整数集的一个函数f,且使得当d(u,v)=1时,有|f(u)-f(v)|≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v∈V(G)}的最小值.定义了点接拟梯子,并完全确定了点接拟梯子的L(2,1)-标号数.  相似文献   

8.
设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的。设G是一个阶n≥4的连通无三角图。本文证明了若G中任意满足dist(u,v)=2的点对u,v∈V(G)有d(u)+d(v)≥2[n+2/4]+3,则G是超级-λ'的。最后,举例说明该结论是最好的。  相似文献   

9.
给出了λ5-最优图的邻域交条件:设G是一个阶至少为10的连通图,对G中任意一对不相邻顶点u和v,若u,v均不在三角形中,有|N(u)∩N(v)|≥6,若u或v在三角形中,有|N(u)∩N(v)|≥9,则G是λ5-最优的;若G中任意一对不相邻顶点u和v满足|N(u)∩N(v)|≥7,任意一条边xy满足|N(x)∩N(y)|≤3,则G是λ5-最优的.  相似文献   

10.
图G的一个L(2,1)-标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)| ≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v ∈ V(G)}的最小数.本文定义了拟梯子,并完全确定了拟梯子的L(2,1)-标号数.  相似文献   

11.
设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.  相似文献   

12.
设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))~(1/2))]+((2p-1)~(1/2))+1.  相似文献   

13.
简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u=u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.  相似文献   

14.
设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.  相似文献   

15.
关于可平面图的3可选择性的一个注记   总被引:1,自引:1,他引:0  
给图G=(V,E)的每个顶点v∈V分配一个可用色集L(v),称L={L(v)|v∈V}为G的一张色列表,若对每个顶点v∈V,都可以从L(v)中找到一种颜色φ(v)染给v,使得φ(x)≠φ(y)对任意边xy∈E成立,则称G是L可染的。若对G的任意一张满足|L(v)|≥k对所有v∈V成立的色列表L,G都是L可染的,则称G是k可选择的。本文运用Discharging方法证明了每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3可选择的。  相似文献   

16.
图G=(V,E)的Wiener极性指标是图G中距离为3的无序点对的数目。图G和H的点corona图,记为G°H是取G的一个拷贝和|V(G)个H的拷贝,然后把G的每个点和其相对应拷贝的每个点相连而得到的图。图G和H的边corona图,记为G◇H,是取G的一个拷贝和|E(G)|个H的拷贝,然后把G的每条边的两个点和其相对应拷贝的每个点相连而得到的图。本文给出两个图的corona乘积图的Wiener极性指标。  相似文献   

17.
一类单圈图的优美性和平衡性   总被引:1,自引:0,他引:1  
设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,2,…,|EI|}的一个单射;(2)由L’(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L’是G的边集E到{1,2,…,|EI|}的一个双射.进一步,若存在正整数c,使得对每一个uv ∈ E(G)满足L(u)≤c〈L(v)或L(w)≤c〈L(u),则称L为图G的平衡标号,其中c为平衡特征.主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征.  相似文献   

18.
一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号