共查询到20条相似文献,搜索用时 89 毫秒
1.
对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。 相似文献
2.
刘建农 《青岛大学学报(自然科学版)》1994,7(1):44-48
A.Ital和M.Rodeh给出了两个关于图的圈覆盖的猜想:(i)任意2-边连通图G=(V,E)有困覆盖C,使l(C)≤|E|+|V|-1;(n)任意2-边连通图有困覆盖,使图的每条边至多被覆盖两次.本文证明了猜想对平面图和2-边连通没有3-边割的图成立,并给出了一与两猜想等价的条件.同时也对著名的2-圈覆盖猜想作了讨论. 相似文献
3.
4.
5.
H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性. 相似文献
6.
证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数. 相似文献
7.
8.
若G是2-连通图,如对G中任何两个距离为2的点υ,ν都有d(υ)+d(ν)≥λ-1(5≤λ≤|V(G)|),则除了两类图外,G的最长圈的长至少为λ。 相似文献
9.
10.
沈传锦 《山西师范大学学报:自然科学版》2010,(4)
探讨路与圈的笛卡尔乘积图的消圈问题,对一般的路与圈,根据引理1及推论1推导出它们的笛卡尔乘积图的消圈数的一个紧的下界;进而对一些特殊的路与圈,推导出它们的笛卡尔乘积图的消圈数的准确值. 相似文献
11.
阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数,得到如下结果:(1)设A包含于E(Kn,n),则当Kn,n[A]≌K1,j或Kn,n[A]≌K2时,Kn,n-A是由它的圈长分布确定;(2)设A包含于E(Kn,n,|A|=4,n≥11,则Kn,n-A是由它的圈长分布确定的。 相似文献
12.
田双亮 《西北民族学院学报》2005,26(2):1-3
通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图. 相似文献
13.
14.
莫降涛 《广西大学学报(自然科学版)》1996,21(2):104-106
设v是图G=(V,E)的顶点,若存在顶点u∈V-{v},使子图G[N(v)∪{u}中任意一对顶点的距离不超过3,则称v是G的弱局部连通顶,点。设G是非平凡的连通无爪图,且它的任一顶点割均钫含一个弱局部连通顶点,则G包含Hamilton圈。 相似文献
15.
用张存铨在文[2]中的方法!本文通过疏远边的度和给出k-连通无瓜图中存在汉密尔顿圈和控制圈的充分条件,作为文中定理的推论,证明了若对任意■∈E(G) d(k)+d(v)≥3n/k-6,则G有汉密尔顿圈;若对任意■∈E(G) d(k)+d(v)≥3n/(k+1)-3,则G有控制圈,这里G是k-连通无爪图。 相似文献
16.
17.
18.
图X称为弱点传递图,如果X的自同态幺半群End(X)在顶点集V(X)上的作用是传递的.证明了弱点传递图X与一族相互同态等价的弱点传递图{Yx|x∈V(X)}的广义字典序积仍为弱点传递的. 相似文献
19.
Ramsey极图的性质 总被引:5,自引:2,他引:5
黄益如 《上海大学学报(自然科学版)》1995,1(3):237-239
本文在引进Ramsey数R(m,n)的饱和极图G(m,n)的概念后,证明了G(3,n)中每个顶点必至少是一个五边形的顶点以及G(3,n)中至少含有个互不相交的五边形等定理;最后还证明了一个新的下界定理,从而改进了一批Ramsey数的下界,例R(4,15)≥122,R(5,9)≥99等. 相似文献
20.
阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数,作者得到如下结果:设n≤r≤min{n 6,2n-3},则Kn,r是由它的圈长分布确定的。 相似文献