首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献，搜索用时 687 毫秒
1.
图G的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上.图G的最优3-pebbling数f'3(G)是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列pebbling移动把三个pebble移到任何一个指定的顶点上.本文给出了路的的最优3-pebbling数的结论及其证明.  相似文献   

2.
图G的pebbling数f(G)是指在一个图G的顶点上以任意方式放置若干个pebble数目的最小值,满足通过一系列的pebbling移动使得任一指定目标顶点能得到一个pebble,而pebbling移动是从一个顶点处移走两个pebble并把其中的一个移到与其相邻的一个顶点上.文章定义了将两个图的直径端点之一粘接生成的一类粘接图,主要计算了一些粘接图的pebbling数,发现了两类满足pebbling数直径下界的图.  相似文献   

3.
图G上的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上.图G的最优pebbling数fopt(G)是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任何一个指定的顶点上.本文给出了C3×Cn的最优pebbling数.  相似文献   

4.
如果图G的每一个导出匹配都包含在图G的一个完美匹配中,则称图G是导出匹配可扩的.用T(G)表示图G的韧度,文章的主要结论是:设G是有2n(n≥3)个顶点的非完全图,如果G是导出匹配可扩的,则2/(n-1) ≤T (G) ≤n-1;对于任意满足2/(n-1) ≤p/q≤n-1,p+q≤2n,1≤q≤n-1的数p/q,都有韧度为p/q的导出匹配可扩图.  相似文献   

5.
笛卡儿积图P2n×Pm与P2n×Cm的gnd-染色   总被引：1，自引：1，他引：0  
设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.文章讨论了笛卡儿积图P2n×Pm和P2n×Cm的gnd-染色,并给出了相应色数.  相似文献   

6.
令简单图G =(V ,E)是有p个顶点q条边的图 .假设G的顶点和边由 1 ,2 ,3,… ,p +q所标号 ,且f:V∪E {1 ,2 ,… ,p+q}是一个双射 .如果对所有的边xy ,f(x) +f(y)+f(xy)是常量 ,则称图G是边幻图 (edge magic) .文 [1 ]中猜测树是边幻图 .本文证明了三路树P(m ,n ,t)当m ,n ,t为偶数且相等时为边幻图 .  相似文献   

7.
树在图论研究以及复杂网络研究中常常用到.记号nd(G)表示图G中顶点度数为d的顶点的数目.本文利用树T的1度顶点个数可以由公式n1(T)=2+△(G)+D(G)n+1.对平面图G,它的面数(G)满足2(G)=4+d3Σ(d-2)n(dG).  相似文献   

8.
设G为n阶的连通k(k 3)圈图,λ1(G)是图G的laplacian矩阵的最大特征值.本文讨论了圈长为3的k圈图的最大特征值与其顶点数及各顶点的悬挂边个数之间的关系.  相似文献   

9.
一、选择题(共4小题,每小题6分,满分24分)图11.数学中,为了简便,记1 2 3 … (n-1) n=Σni=1i,1×2×3×…×(n-1)×n=n!,那么2006!2005! Σ2005i=1i-Σ2006i=1i的值是()。A、0;B、1;C、2005;D、2006.2.如图1,一枚棋子放在七边形ABCDEFG的顶点A处,现顺时针方向移动这枚棋子10次,移动规则是:第K次依次移动K个顶点,如第一次移动1个顶点,棋子停在顶点B处,第二次移动2个顶点,棋子停在顶点D处,依这样的规则,在这10次移动的过程中,棋子不可能停到的顶点是()。A·C,E,F;B·C,E,G;C·G,E;D·E,F.3.已知一列数a1,a2,a3,…,an中,a1=0,a2=2a…  相似文献   

10.
设G为一个n阶图,G的邻接矩阵A(G)的特征值为λ1,λ2,…,λn,Estrada指数被定义为EE(G)=Σni=1eλi。该文确定了如下树类中Estrada指数的极小图,此类中的树均有n个顶点且恰好包含有两个最大度为△的顶点。进一步提出了一个关于如下树类中Estrada指数的极小图的猜想,此类中的树均有n个顶点且恰好包含有k个最大度为△的顶点。  相似文献   

11.
令图G是无孤立点的无向图。 V（G）是图G的顶点集,D是V（G）的真子集。如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集。 G中最小全控制集的顶点数称为G的全控制数,记为γt（G）。参考已有全控制数的知识及笛卡尔乘积 Cm□Cn、Pm□Pn 的全控制数的相关结论,利用γt（Cm□Cn ）≤γt（Pm□Cn ）≤γt（Pm□Pn ）这一不等式给出了Cm□Pn（m =3,4）、Pm□Cn（n =2,4）的全控制数。  相似文献   

12.
Mycielski引入了对于图G的一类新的变换图μ（G）,称为G的Mycielskian.这类变换图的推广是广义Mycielskian图μm（G）,m是正整数.如果每个最小点割（最小边割）孤立G的一个点,则称图G是超连通的或超-κ（超边连通的或超-λ）.证明结果显示：设G是连通图且｜V（G）｜≥3条件下,μm（G）是超-κ的充要条件是δ（G）＜（m＋1）κ（G）;μm（G）是超-λ的充要条件是G（≠）K2,即G不是一条边.  相似文献   

13.
两个不交图G与H的联G+H是指顶点集为V(G)∪V(H),边集为E(G)∪E(H)∪{xy|x∈V(G),y∈V(H)}的图.证明了当n=m+1时,联图Om+Cn是第二类图,否则,Om+Cn是第一类图;当|n-m|=1时,联图Cm+Cn是第二类图,否则,Cm+Cn是第一类图.  相似文献   

14.
给出了一类特殊拓扑空间一θ-复形和θ-复形的图的定义,然后讨论了日一复形的图结构,从而更加形象直观地描述了口一复形中顶点、开滤子与闭滤子之间的关系,并证明了结论：（1）设K是口一复形,G为其图,则对任意的中心滤子点U,有2≤dG（u）≤3;（2）设K是θ-复形,G为其图,则在G中不存在循环图;（3）设θ-复形K的图G为树,则在G中任意两个中心滤子点均由唯一的途径连接;（4）设u为中心滤子点,口为边滤子点或者顶点,则有d（u,v）=2m-1,m∈ω．  相似文献   

15.
松弛均匀着色是松弛着色的一类特殊情况,它要求任意两个色类的顶点数之差至多为1．d-退化图是指每个导出子图都存在度至多为d的顶点的图．证明了若顶点数位rt的d-退化图G的最大度至多为△,且K≥18d,n≥17△．则G存在均匀（k-1,1）着色．  相似文献   

16.
若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图．  相似文献   

17.
主要研究了一类特殊图——冠图的点可区别的均匀边染色,讨论过程中主要采用组合的方法,分别研究不同情况下该类图的染色方法,验证点可区别的均匀边染色数界的猜想μ（G）≤X＇vde（G）≤μ（G）＋1．该方法对解决此类图的染色均是正确有效的．  相似文献   

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

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