共查询到20条相似文献,搜索用时 125 毫秒
1.
高炜 《山西大学学报(自然科学版)》2012,(4):626-631
设G是一个图,若去掉G中的任意n′个顶点的剩余子图仍是分数k-消去图,则称G是一个分数(k,n′)-临界消去图.文章证明了当t(G)≥((k2-1)(n′+1))/k,且n>k+n′+1时,G是分数(k,n′)-临界消去图. 相似文献
2.
设g和f是两个定义在图G顶点集上的整值函数,使得对G的所有顶点x有g(x)≤f(x)。证明了以下结果:如果G是一个(mg+r,mf-r)-图,1≤r相似文献
3.
《南通大学学报(自然科学版)》2017,(2)
设整数k2,k-太阳图S(Ck)是一个由k-圈图的每个顶点向外伸出一条悬挂边得到的图.v阶k-太阳系是完全图Kv到k-太阳图的一个分解.如果v阶k-太阳系存在一个v阶自同构,则称该k-太阳系是循环的;如果v阶k-太阳系存在一个包含一不动点和一长为v-1轮换的自同构,则称该k-太阳系是1-旋转的.应用差的方法直接证明了当v≡1(mod 4k)时,存在v阶循环的k-太阳系;当v≡0(mod 4k)时,存在v阶1-旋转的k-太阳系,其中k=7,9,11,13. 相似文献
4.
对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图. 相似文献
5.
图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2. 相似文献
6.
《辽宁大学学报(自然科学版)》2018,(4)
设G是一个有至少2个顶点连通图.当火在G的某个顶点v处燃起时,消防员可以选择k个顶点进行防护.接着在每次时间间隔内,火源传到那些未被防护下来的着火顶点的邻点.火源与消防员交替移动直到火无法传播.消防员的任务是尽可能救多的顶点.图G的k-存活率定义为G的顶点随机着火时消防员一次可以救k个顶点的整个防火过程可救下的顶点的平均存活率.首先把IC-图转化为平面图,然后在平面图上运用权转移方法,证明了:每一个IC-图的5-存活率大于1*10. 相似文献
7.
王湘平 《湖北民族学院学报(自然科学版)》2009,27(1)
设图G是一个简单图,图G的补图记为G.如果G的谱完全由整数组成,就称G是整谱图.讨论了当u1=a+b且a-1>b时,aKa U(3B+2)Kb,b不是整谱图;当u1=a+b且a≤b时,aKa UBKb,b(a=1,B=1,a=3或2,b=6)是整谱图. 相似文献
8.
9.
对于无向简单图G及正整数a1,…,ak,记G→(a1,…,ak)v当且仅当对于图G的任意一种顶点k染色,一定对某个i∈{1,…,k}存在顶点全染着颜色i的完全子图Kai.对于p>m ax{a1,…,ak},定义Fv(a1,…,ak;p)=m in{V(G):G→(a1,…,ak)v,Kp G}为顶点Folkm an数.证明关于顶点Folkm an数Fv(k,k;k 1)的新的迭代不等式,并推广K olev和N enov的一个关于多色顶点Folkm an数的不等式. 相似文献
10.
设G是简单连通图,顶点集为V(G).图G的度基尔霍夫指数定义为图G中所有顶点对的度与顶点之间的电阻距离乘积的和.棒棒糖图Ln,k是路Pn-k的一个端点连接到圈Ck的一个顶点得到的一类特殊的单圈图.给出首先给出Ln,k的度基尔霍夫指数计算公式,然后刻画了相应的极图. 相似文献
11.
任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑d(G,k)xk k≥0,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi}ni=1是一个两两不交的图的集合,并且Vi,Vi∈V(Gi),所谓链图C(G1,G2,…,Gn)≡C(G1,G2,…Gn;v1,w1,v2,w2,…,vn,wn)指的是将各点对wi和vi+1粘合起来而得到的图,其中i=1,2,…,n-1。文章得到了链状割点图的Hosoya多项式,并且,作为引理,并给出了树的Hosoya多项式。 相似文献
12.
阮妮 《邵阳学院学报(自然科学版)》2009,6(4):9-11
G是一个Kn-e图,e∈E(Ka)。设σ2(G)表示不相邻顶点度和的最小值.令|V(G)|=n=∑^ki=1 a,并且σ2(G)≥,n+k-1.证明对于图G中任意的k个顶点v1,v2,…vk。存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有|V(Pi)|=ai.并且vi是Pi的一个端点. 相似文献
13.
如果G的任意s个点的导出子图中至少含有t条独立边,则称图G为强-[s,t]图。本文证明了以下结果:设G是k-连通的强-[k+4,2]图,且δ≥k+1,则G或者有Hamilton路或者同构于(∪k+2i=1Hi)∨Gk,其中Hi≌K2,i=1,2…k+2,Gk是含有k个点的任意图。 相似文献
14.
15.
设Gi是一个极大边连通的与Ki-正则图,且ki≥3,i=1,2,证明了:如果围长g(Gi)≥4,则其笛卡尔乘积图G1□G2是超级3-限制边连通的;同时提出了在特定条件下笛卡尔乘积图Gm□G和K2□G是超级3-限制边连通的充要条件。 相似文献
16.
李雪峰 《安徽大学学报(自然科学版)》2008,32(4)
令K4(i,j,k,l,m,n)表示图G的色多项式,如果P(G)=P(H),称G和H色等价;如果对任意图H,当P(H=P(G))时,都有H和G同构,称G是色唯一的.令K4(i,j,k,l,m,n)表示两两三度点间的路长分别为i,j,k,l,m,n的K4-同胚图.作者对集合{i,j,k,l,m,n}由3个不同值组成,且等于每个值的路都恰有2条的K4-同胚图的着色进行了研究,得到了1类色唯一的K4-同胚图. 相似文献
17.
完全二部图K5,n的点可区别IE-全染色 总被引:2,自引:0,他引:2
设G是简单图,图G的一个k-点可区别IE-全染色(简记为k-VDIET染色)f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,且满足:A↓uv∈E(G),有f(u)≠f(v);A↓u,v∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE-全色数。 相似文献
18.
完全三部图K(n- k,n,n)的色性 总被引:1,自引:1,他引:0
设P(G,λ)表示简单图G的色多项式;若对任意简单图H 满足P(H,λ) = P(G,λ),都有H 与G同构,则称G是色唯一图;设K(m ,n,r) 表示完全三部图;本文证明了:(1) 若n > k + k2/3,则图K(n - k,n,n) 是色唯一的,(2) 若n ≥8,则K(n - 4,n,n) 是色唯一的; 相似文献
19.
图是极大限制边联通的充分条件 《山东科学》2015,28(3):80-83
设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|[X,X]|:|X|=k,G[X]连通},其中X=V(G)\X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。 相似文献
20.
胡杏 《邵阳学院学报(自然科学版)》2008,5(1):12-14
设G是-个简单图,g和f是两个定义在V(G)上的整数值函数,且对所有的x∈V(G)都满足g(x)≤f(X).如果删除G的任何k个顶点后,图G的其余部分含有-个(g,f)因子,那么称图G为一个(g,f,k)-临界图.本文给出了-个图是(g,f,k)-临界图的-个充要条件,并对这些奈件的应用作了讨论。进-步,本文研究了(g,f,k)-临界图的性质. 相似文献