共查询到19条相似文献,搜索用时 78 毫秒
1.
侯旻 《南京工程学院学报(自然科学版)》2006,4(3):11-15
一个图H称为一个双星(Double Star),当H由2个不变的星K1.m1,K1,m2加上连接它们最大度点的一条边所构成.图G的一个支撑子图F称为一个双星(DS)因子,当F的每一个连通分支是一个双星.本文研究完全偶图Km,n的DS-因子计数,给出了Km,n的DS-因子计数公式. 相似文献
2.
给出了完全三部多重图Kn,n,n存在S4-因子分解的充分必要条件是:n0(mod12/d),其中d=gcd(,12)。 相似文献
3.
C_t表示长度为t的圈,一个图G=(V,E)的一个C_t-因子分解是边集E的一个分划{E_1,E_2,…,E_k},使得■i∈{1,2,…,k},支撑子图(V,E_1)的每个分枝都同构于C_t,(V,E_1)被称为G的一个C_t-因子。本文讨论了完全图的圈因子分解,主要结果为:若p=(2n 1)~m。则完全图Kp存在一个C_(2u 1)-因子分解。 相似文献
4.
1-因子或完美匹配的计数是NP-难的,利用S~((n))-因子的表示公式和分支分析方法研究1-因子或完美匹配具有理论和实际意义.首先,得到无K_3子图的图中1-因子计数公式和组合恒等式;其次,导出1-因子或完美匹配存在和不存在的充分必要条件;最后,得出一个结论:存在连通图使得它的1-因子的个数大于任意的自然数N. 相似文献
5.
6.
设g和f是定义在二分图G的顶点集V(G)上的两个整数值函数且对每个x∈V(G)有g(x)≤f(x).证明了若H是二分图G的任一m-星,则G有一个(g,f)-因子分解与H正交的充要条件是G为一个(mg,mf)-图. 相似文献
7.
讨论了完全二部图、完全图和完全多部图的Mycielski图的星全染色问题,得到了它的星全色数. 相似文献
8.
侯旻 《南京工程学院学报(自然科学版)》2005,3(2):1-5
图G的一个支撑子图F称为G的一个(1,2)因子,当F的每一个连通分支是路或圈.若G能够分解成边不交的(1,2)—因子的并,则称这样的并为G的一个(1,2)—因子分解.完全偶图Km,n存在具有最小边数和最大边数的(1,2)—因子,定理1和定理2给出了Km,n的上述(1,2)—因子分解. 相似文献
9.
图G的孤立韧度定义为I(G)=min{|S|/i(G-S)|S■V(G),i(G-S)≥2},若G不是完全图;否则,令I(G)=|V(G)|-1.本文证明了:若G的最小度满足δ(G)≥a n以及孤立韧度I(G)≥a-1 (a 2n)/b,其中a,b,n都是非负整数且1≤a相似文献
10.
11.
《内蒙古师范大学学报(自然科学版)》2015,(5)
确定一个图的扩容图的自同构群是一个比较困难的问题.通过完全图的完全扩容图的自同构群与完全图的自同构群之间的特殊关系,推导出完全图的完全扩容图的自同构群是一个非本原群,在此基础上进一步确定了完全图的完全扩容图的自同构群. 相似文献
12.
顾成扬 《华侨大学学报(自然科学版)》2005,26(2):222-224
讨论完全图Kn分解成4个顶点的路、星和圈的存在性.给出完全图Kn存在{C4,S4},{P4,C4),{P4,S4},{P4,S4,C4}-分解以及强制分解的充要条件. 相似文献
13.
何建锋 《云南民族大学学报(自然科学版)》2007,16(3):216-218
给图G的每条边e都赋一个权w(e),所得的赋权图记为G(w).在G(w)中,顶点v的标号f(v)等于与顶点v相邻各边的权之和,当各顶点标号相异时,称G(w)是非正则的.G(w)的非正则和是在所有以图G为基础图的非正则图中,各顶点标号的和为最小时的值,记为∑(G).若非正则和∑(G)=nδ 2n,则称图G连续.利用图的权矩阵,讨论了图nK4m、nK5m、nK6m和nK7m的连续性. 相似文献
14.
连通图G所谓的l-边-连通度(Z—edge—connectivity),就是使图C成为至少l个分支所必须去掉的最少边数,记作λl(G),即λ1(G)=min{|E’|:E’真包含E(G),ω(G—E’)≥l}.研究了完全2-分图的l-边-连通度,得到了定理:设G=G[V1,V2]是一个完全2-分图,|V1|=r,|V2|=s,r+k=s,k≥0为整数.则图G的(k+2)-边-连通度为(k+1),即λk+2(G)=r(k+1). 相似文献
15.
16.
研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性. 相似文献
17.
18.
19.
讨论了求解极大完全子图算法的形式化,给出了带权的完全图中求最小权Hamilton回路优化算法的软件实现。 相似文献