共查询到20条相似文献,搜索用时 15 毫秒
1.
染色问题是具有重要实际意义和理论意义的研究课题,是图论的主要研究内容之一.图染色的基本问题就是确定图的各种染色方法及其色数.讨论了一类联图Kc4∨ Kt的点可区别正常边染色与色数,并对更一般的联图Kcn ∨ Kt的点可区别正常边染色问题进行了研究. 相似文献
2.
讨论了图K4,4∨Kt的点可区别正常边染色及其色数.利用正多边形的对称性构造染色以及组合分析的方法.确定了图K4,4∨Kt的点可区别正常边色数,得到了:当t是奇数且t≥3以及t是偶数且2≤t≤32时,χ′s(K4,4∨Kt)=t+8;当t是偶数且t≥34时,χ′s(K4,4∨Kt)=t+9. 相似文献
3.
图的一个正常边染色被称为点可区别边染色若任意两点的色集合不相等,其所得的最少颜色数称为点可区别边色数.应用平行线法研究了图K2n\E(K1,m)(n≥2)的点可区别边染色,并得到了其点可区别边色数,进一步验证了图的点可区别边染色猜想. 相似文献
4.
针对图K2n\E(k1,m)的点可区别边色数猜想,设计了一种新型的点可区别边染色算法.根据点可区别边染色的约束条件构建目标函数,利用交换规则进行逐步寻优,直到目标函数的值满足要求时染色成功.同时给出了算法的执行步骤、分析和测试结果.实验结果表明,该算法验证了猜想是成立的. 相似文献
5.
《西南大学学报(自然科学版)》2016,(10)
针对图K_(2n)\E(k_1,m)的点可区别边色数猜想,设计了一种新型的点可区别边染色算法.根据点可区别边染色的约束条件构建目标函数,利用交换规则进行逐步寻优,直到目标函数的值满足要求时染色成功.同时给出了算法的执行步骤、分析和测试结果.实验结果表明,该算法验证了猜想是成立的. 相似文献
6.
根据T-型六角系统链H结构的性质以及2度点的排列特点,用π(H)+1种颜色给出了p(≥4)阶H中2度点的点可区别边染色算法,紧接着分析其3度点的染色特点,通过调整个别边的颜色,最终证明H(p≥4)的点可区别色数不超过π(H)+1.另外,当p≤3时,用π(H)种颜色给出具体的点可区别边染色方法,从而证明H的点可区别边色数不超过π(H)+1. 相似文献
7.
8.
针对星、路、圈与完全图之间的关系,讨论了星、路、圈和完全图的多重联图的邻点可区别E-全染色,并给出了它们的邻点可区别E-全色数. 相似文献
9.
利用Lowell Beineke和Richard Ringeisen给出的边共色数的界,研究得到了Sm∨Pn和Sm∨Cn的边共色数. 相似文献
10.
设G是简单图,若图G的全染色厂满足:①Vuv,vw∈E(G),有f(uv)≠f(vw);②V uv∈E(G),u≠v,有f(u)≠f(v);③Vu,v∈V(G),0〈d(u,v)≤β时,有S(v)≠S(v),这里色集合S(u)={f(u))U{,f(uv)|uv∈E(G),则称,是图G的一个k-D(β)一点可区别I-全染色。用概率方法得到了邻点可区别I-全色数的一个较小上界,并研究了若干Cartesian积图的D(β)一点可区别I-全色数的上界。 相似文献
11.
设G=(V,E)是简单图,f是从VUE到{1,2,…,k}的一个映射,其中k是正整数.对任意x∈V,令C(x)={f(x)}U{f(y)| y∈V,y和x相邻}U{f(e)| e∈E,e和x相关联},称之为x在f下的色集合.若:(i)对任意u v∈E,f(u)≠f(v),有f(u)≠f(uv),f(v)≠f(uv);(ii)对任意uv,uw∈E,7v≠w,有f(uv)≠f(uw);(iii)对任意u,v∈V,u≠v,有C(u)≠C(v),则称f是图G的一个使用了k种颜色的点强可区别全染色,简记为k-VSDTC.称xvst(G)=min{k|G存在肛VSDTC}为G的点强可区别全色数.得到了完全二部图K4.n(n>4)的点强可区别全色数. 相似文献
12.
应用构造具体染色的方法给出了两类3-正则Halin图的邻点可区别Ⅰ-全色数. 相似文献
13.
14.
设图G(V,E)为简单图,k是一个正整数,f是V(G)U E(G)到[1,2,…,k]的一个映射,如果(V)uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),且当C(u)=[f(u)]U[f(uv) uv∈E(G)]时,C(u)≠C(v),则称f是图G的邻点可区别E全染色,称此最小的数k为图G的邻点可区别E全色数.通过考虑图的结构关系,研究得到了路、圈与完全图笛卡尔积图Pm×Kn、Cm×Kn的邻点可区别E-全色数. 相似文献
15.
如果图G有一个合理边着色,使得图G中任意两个相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色.有一个准强边着色的图称为网络图(或准强边着色图).使图G有一个准强边着色的最小色数称为网络图(或准强边着色图)的准强边色数,它被记为χ′qs(G).讨论了网络图的分类问题和网络完全图的计数问题,提出并证明了下述网络图猜想(或准强边着色猜想):如果连通网络图有△(G)≥2,则网络图G的准强边色数有△(G)≤χ′qs(G)≤△(G)+3. 相似文献
16.
17.
18.
设G是一个n阶图.众所周知,两个图G和H色等价当且仅当它们的补图伴随等价.可见伴随多项式是研究图的色多项式的一种有效途径.本文通过比较伴随多项式的最小根,最终计算了K 1∪Pm的伴随等价图的个数以及它的伴随等价图类.进一步,计算了(K1∪Pm)的色等价图的个数以及它的色等价图类,这里K 1和Pm分别表示一个孤立点和m个... 相似文献
19.
用mK2,3表示m个完全二部图K2,3的点不交的并,给出了mK2,3的点可区别全色数,证明了对任意的m≥4,[k-13]<3m≤[3k],有χvt(mK2,3)=k. 相似文献
20.
根据路与完全图(星、扇、轮、路、圈)构造的冠图的结构性质,应用分析和构造函数法研究了邻点可区别V
全染色,得到了路与完全图(星、扇、轮、路、圈)构造的冠图的邻点可区别V 全色数. 相似文献