共查询到20条相似文献,搜索用时 203 毫秒
1.
许振宇 《济南大学学报(自然科学版)》2008,22(2):197-199
图G膨胀图是指将G的每一个点都用一个完全图替换,且取代两个不同顶点u和v的完全图上的两点相邻当且仅当u和v是相邻的;若取代每个顶点的完全图都是同阶的,则称此膨胀图为一致的.证明了圈的一致膨胀图的关联色数不超过Δ(G) 2. 相似文献
2.
对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。 相似文献
3.
研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性. 相似文献
4.
文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。 相似文献
5.
王志坚 《苏州科技学院学报(自然科学版)》2000,(2)
对于图G和图H ,Ramsey数r(G ,H)定义为最小正整数 p ,使得完全图Kp 用红、蓝两色作任意边着色后 ,总含红色子图G或蓝色子图H。以mG记m个图G的不相交并 ,Ck 记长度为k的圈 ,对于正整数m、n ,n≥m≥ 1 ,本文确定了Ramsey数r(mC3 ,nC4)。 相似文献
6.
图G的t-pebbling数ft(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列pebbling移动把t个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点上移走两个pebble,而把其中的一个移到与其相邻的一个顶点上,本文确定了完全二部图t-pebbling数,作为推论给出了完全K部图的t-pebbling数。 相似文献
7.
对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,或者存在红色子图G,或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1,Fn=K1+nK2.证明了当m≥1且n≥max{2,3 m-2},R(Bm,Fn)=4n+1;当n≥38,R(F2,K2,n)=2n+3. 相似文献
8.
董琳 《同济大学学报(自然科学版)》2010,38(5):766-766
图G的Ramsey数r(G)是指最小的自然数N,满足当n≥N,对完全图Kn的边进行红蓝二着色时总包含单色的图G.对于完全二部图Km,n,给出了当n充分大时,r(Km,n)≥2m(n-n0.525)的一个代数构造的证明. 相似文献
9.
完全图的广义Mycielski图的邻点可区别的全色数 总被引:1,自引:1,他引:0
对图G的一个k-正常全染色法,若满足相邻点的点染色和关联边的色集合不同时,称该染色法为邻点可区别全染色,其所用小染色数k称为G的邻点可区别全色数.得到了完全图Km的广义Mycieski图Mn(Km)(n≥1,m≥3)的邻点可区别全色数. 相似文献
10.
对于图G(V,E)的正常七一全染色/称为G(V,E)的七一均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.Xet(G)=min{k|G有七一均匀全染色|称为G的均匀全色数.利用均匀边染色的相关结论,探讨了路Pn与完全二部图km,n的联图PnVm,n的均匀全色数. 相似文献
11.
堵根民 《内蒙古师范大学学报(自然科学版)》1997,(2):9-12
给出了完全k部图是Cordial图的充要条件,并给出此类Cordial图的Cordial标号,给出n阶Cordial图的最大边数,并构造了相应的极图;给出正则图是Cordial图的必要条件;解决了轮的Cordial问题。 相似文献
12.
图的染色理论是图论的一个重要分支。本文使用分析的方法得到了轮和完全等二部图联图的全色数、均匀全色数和邻点可区别边色数。 相似文献
13.
14.
给出了树宽≤2的图也就是系列并行图的几个等价刻画。证明了对有限图G(可以有环有重边)以下四断言彼此等价:(1)G是系列并行图,(2)G的任一个minor至少有一个点的度≤2;(3)G不以4阶完全图为minor;(4)G无子图同胚于4阶完全图。 相似文献
15.
王世琪 《南京大学学报(自然科学版)》2007,24(2):238-243
本文将在逻辑Lω1,ω中把完全二叉树理论的可数模型刻画到同构并给出它们的 Scott 语句具体形式.证明了完全二叉树理论的可数模型的胞腔性质. 相似文献
16.
黄迎秋 《苏州大学学报(医学版)》1999,15(3):17-21
给定无孤立点的简单图G,完全图K的G-覆盖定义为一个序偶(V,F),其中V为K_v的顶点集,F为K_v的一族子图,使得F中每一个子图都与G同构且K_v的每一条边至少出现在F的一个子图之中.完全图K_v的G-覆盖中所含的最少的子图个数称为它的G-覆盖数,记作(ν,C).本文对五个顶点,五条边的4个图G,完全确定了C(ν,G)值. 相似文献
17.
证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3. 相似文献
18.
19.
20.
准补图的紧性和超紧性 总被引:2,自引:2,他引:0
张秀平 《北京师范大学学报(自然科学版)》1999,35(3):316-319
推广了补图的概念,找到了另一类紧图和紧超紧图,对于(m,k)圈的准补图是否为紧图或超紧图作了详尽的讨论。 相似文献