导读:本文包含了满着色论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:标号,乘积,正则,广义,分配,频率,完美。
满着色论文文献综述
赵小玲,吕长虹[1](2010)在《一类连通可满着色图的L(2,1)标号》一文中研究指出令G=(V(G),E(G))是一个简单图,Mp(G)为图G的广义Mycielski图.图G的L(2,1)标号数记作λ(G),定义为λ(G)=min{k|G有一个k-L(2,1)标号}.一个连续的L(2,1)标号是一个L(2,1)标号,使得所用的标号是连续的,相应的标号数记作-λ(G).凡是满足λ(G)=-λ(G)的图称为可满着色图.给出了一些特殊图的广义Mycielski图的L(2,1)标号数,从中发现一些广义Mycielski图为可满着色图,并由此猜想广义Mycielski图(除Mp(Kn)之外)为可满着色图.(本文来源于《扬州大学学报(自然科学版)》期刊2010年04期)
赵小玲[2](2008)在《广义Mycieiski图的L(2,1)标号与可满着色图》一文中研究指出图的标号问题是图论中一个重要的研究分支,在现实生活中有着广泛的应用。对于一般图,确定它们的标号数的精确值是NP-hard问题。对于一些特殊图,我们可以探讨它们的标号数的精确值和上下界。本文主要介绍了图的L(2,1)标号问题的研究进展和本人在这方面所作的工作,主要包括以下叁个部分:(1)研究了广义Mycielski图的L(2,1)标号数;(2)讨论了具有λ(G)=(?)(G)性质的图的特殊结构;(3)讨论了约束条件推广为叁个的图的标号问题。在第一部分中,本文得到了如下一些特殊图的广义Mycielski图的L(2,1)标号数的结论:(1)令M_p(P_n)是路P_n的广义Mycielski图,则λ(M_p(P_n))=4当n=2,p≥2时;λ(M_p(P_n))=5当,n=3,p=2时;λ(M_p(P_n))=6当,n≥3,p≥3时。(2) M_p(K_(1,n-1))是星图K_(1,n-1))的广义Mycielski图(n≥4),则λ(M_p(K_(1,n-1)))=2n-1当p=2时;λ(M_p(K_(1,n-1)))=2n当p≥3时。(3)令M_p(K_n)是K_n的广义Mycielski图,则λ(M_p(K_n))=4当n=2时;λ(M_p(K_n))=3n-2当n≥3时。(4)令M_p(C_n)是圈C_n的广义Mycielski图,则λ(M_p(C_n))=7当,n=3,4,5时。在第二部分中,本文讨论了连续标号问题。在[9]中,吕长虹等人证明了(1)G是一个顶点数n边数m的图,若m≤n-2,则λ(G)=(?)(G),除非G是一些K_2的不交并。(2)G是一个阶数为n的图,若C(G)≥[(n+1)/2],则λ(G)=(?)(G)。这两种具有λ(G)=(?)(G)性质的图均为不连通的图。本文考虑了一些连通图的广义Mycielski图的特殊结构,得到了一类具有λ(G)=(?)(G)性质的连通图。在第叁部分中,本文研究了约束条件推广为叁个的标号问题。讨论了Halin图和完全图的广义Mycielski图的L(3,2,1)标号数的上界,得到了如下的结论:(1)令G是最大度为△的Halin图,则λ_(3,2.1)(G)≤5△+16。(2)令M_p(K_n)是K_n的广义Mycielski图,则λ_(3,2,1)(M_p(K_n))≤7n-4。(本文来源于《华东师范大学》期刊2008-10-01)
陈磊[3](2007)在《可满着色图和最优标号问题》一文中研究指出图的染色问题是图论中最基本,也是最重要的问题之一。而图的标号问题作为图的染色问题的推广在现实生活中有广泛的应用。本文主要讨论了图上的两种标号问题:L(2,1)-标号和最优标号。给定一个无向图G,G的一个L(2,1)-标号是指从其顶点集V(G)到非负整数集的一个映射f,满足:这里d_G(u,v)表示u和v之间的距离。若一个L(2,1)-标号中的所有标号都不超过整数k,则称之为k-L(2,1)-标号。图G的L(2,1)-标号数,记作λ(G),是使得图G存在L(2,1)-标号的最小正整数k。特别地,若G的某个L(2,1)-标号中的标号是连续出现的,则称之为G的一个No-hole L(2,1)-标号。图G的No-hole L(2,1)-标号数,记作(?)(G),是使得图G存在No-hole L(2,1)-标号的最小正整数k。很显然(?)(G)≥λ(G)。在第二章中我们将把注意力放在上述不等式取等号的情况,并把一个满足(?)(G)=λ(G)的图G称为可满着色图,否则称G为非可满着色图。本文第二章将给出一些可满着色图,主要结果有:(1):刻画非可满着色图的基本结构。(2):G是n个顶点m条边的图,如果m≤n-2,则G是可满着色图除非G(?)K_2(其中K=n/2≥2)。(3):G是n个顶点的图,如果它的连通分支数C(G)≥[(n+1)/2],则G是可满着色图。(4):G是n个顶点m条边的图,如果m=n-1,则G是可满着色图除非G(?)K_(1,n-1),L_(1,3)∪aC_3∪bC_6(a+b≥1),K_1∪aC_3∪bC_6(a+b≥1)。(5):G是n个顶点的图,如果它的连通分支数C(G)≥[n/2],则G是可满着色图除非G(?)K_(k+1)∪(k-1)K_1(其中k=n/2)。图的L(2,1)-标号问题在过去十几年中已经得到了广泛而深入的研究。J.R.Griggs和R.K.Yeh([19])给出了路、圈、树等特殊图类的λ值以及最大度为△的一般图的λ的上界△~2+2△,并且猜想对最大度为△≥2的任意图有λ(G)≤△~2。G.J.Chang和D.Kuo([2])证明了对最大度为△的任意图有λ(G)≤△~2+△。D.Král和R.Skrekovski([23])又稍做改进,证明了对任何△≥2的图有λ(G)≤△~2+△-1。最新的结果是由Concalves给出的,对任何△≥3的图有λ(G)≤△~2+△-2。目前已有大量的特殊图被证明满足J.R.Griggs和R.K.Yeh提出的猜想,本文第叁章将给出一些特殊图的L(2,1)-标号数的上界,这些特殊图包括Mycielski图和无爪图,同时也研究了树的L(2,1)-标号数与其补图的L(2,1)-标号数和的上下界。标号图(G,L)由图G和它的标号L∶V(G)→{1,2,…,n}组成,其中n=|V(G)|。在标号图(G,L)中,如果一条路U_1U_2…u_k满足L(u_i)+2≤L(u_(i+1))(i=1,2,…,k-1)或者k=1,则称为不连续增长路。标号图(G,L)中所有的不连续增长路的数目记为d(G,L)。如果一种标号L使得d(G,L)达到最大就称为最优标号。最优标号的问题最先是由M.L.Gargano、M.Lewinter和J.F.Malerba([11])叁个人提出的。他们提出了一个公开问题:给P_n一个标号L使得d(P_n,L)达到最大。后来I.E.Zverovich解决了这个问题,并给出了证明。本文第四章将给出一个简化的证明,并把这个公开问题推广到圈和星图上。(本文来源于《华东师范大学》期刊2007-05-01)
董伟[4](2006)在《有关满着色的一些结果》一文中研究指出图G=(V,E)的一个正常k-着色实际上是将G的顶点划分为独立集,记为∏={V1,V2,…,Vk}.其中Vi,i=1,2,…,k,也称色类.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则v被称为是满色的.如果在G的一个正常k-着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为χf(G).另外,记ψf(G)为使图存在满着色的最大颜色数.本文主要研究了有关满着色的一些性质,并给出一个满着色与完美图之间的结论.(本文来源于《商丘师范学院学报》期刊2006年02期)
董伟,许宝刚[5](2004)在《乘积图与正则图的满着色》一文中研究指出图G=(V,E)的一个正常着色就是将G的顶点划分为独立集,或称之为色类,记为 ={V1,V2,…,Vk}.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则v被称为是满色的.如果在一个正常着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为χf(G).另外,记ψf(G)为使图存在满着色的最大颜色数.在这篇文章中,我们研究了一些乘积图的满着色,得出一些关于正则图的满着色的结果.(本文来源于《南京师大学报(自然科学版)》期刊2004年03期)
董伟[6](2004)在《有关图的满着色》一文中研究指出图G=(V,E)的一个正常k-着色实际上是将G的顶点划分为独立集,记为∏={V_1,V_2,…,V_k)。其中V_i,i=1,2,…,k,也称色类。对于任一色类V_i中的点v,如果它与其余每个色类中至少一个点相邻,则v被称为是满色的。如果在G的一个正常k-着色中,所有点都是满色的,则称这样的着色是满着色。如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为xf(G)。另外,记ψf(G)为使图存在满着色的最大颜色数。在这篇文章中,我们研究了一些乘积图的满着色,得出一些关于正则图的满着色的结果。研究了满着色与完美图的关系,并且对满着色与正常着色的差做了初步的探讨。(本文来源于《南京师范大学》期刊2004-06-30)
满着色论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
图的标号问题是图论中一个重要的研究分支,在现实生活中有着广泛的应用。对于一般图,确定它们的标号数的精确值是NP-hard问题。对于一些特殊图,我们可以探讨它们的标号数的精确值和上下界。本文主要介绍了图的L(2,1)标号问题的研究进展和本人在这方面所作的工作,主要包括以下叁个部分:(1)研究了广义Mycielski图的L(2,1)标号数;(2)讨论了具有λ(G)=(?)(G)性质的图的特殊结构;(3)讨论了约束条件推广为叁个的图的标号问题。在第一部分中,本文得到了如下一些特殊图的广义Mycielski图的L(2,1)标号数的结论:(1)令M_p(P_n)是路P_n的广义Mycielski图,则λ(M_p(P_n))=4当n=2,p≥2时;λ(M_p(P_n))=5当,n=3,p=2时;λ(M_p(P_n))=6当,n≥3,p≥3时。(2) M_p(K_(1,n-1))是星图K_(1,n-1))的广义Mycielski图(n≥4),则λ(M_p(K_(1,n-1)))=2n-1当p=2时;λ(M_p(K_(1,n-1)))=2n当p≥3时。(3)令M_p(K_n)是K_n的广义Mycielski图,则λ(M_p(K_n))=4当n=2时;λ(M_p(K_n))=3n-2当n≥3时。(4)令M_p(C_n)是圈C_n的广义Mycielski图,则λ(M_p(C_n))=7当,n=3,4,5时。在第二部分中,本文讨论了连续标号问题。在[9]中,吕长虹等人证明了(1)G是一个顶点数n边数m的图,若m≤n-2,则λ(G)=(?)(G),除非G是一些K_2的不交并。(2)G是一个阶数为n的图,若C(G)≥[(n+1)/2],则λ(G)=(?)(G)。这两种具有λ(G)=(?)(G)性质的图均为不连通的图。本文考虑了一些连通图的广义Mycielski图的特殊结构,得到了一类具有λ(G)=(?)(G)性质的连通图。在第叁部分中,本文研究了约束条件推广为叁个的标号问题。讨论了Halin图和完全图的广义Mycielski图的L(3,2,1)标号数的上界,得到了如下的结论:(1)令G是最大度为△的Halin图,则λ_(3,2.1)(G)≤5△+16。(2)令M_p(K_n)是K_n的广义Mycielski图,则λ_(3,2,1)(M_p(K_n))≤7n-4。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
满着色论文参考文献
[1].赵小玲,吕长虹.一类连通可满着色图的L(2,1)标号[J].扬州大学学报(自然科学版).2010
[2].赵小玲.广义Mycieiski图的L(2,1)标号与可满着色图[D].华东师范大学.2008
[3].陈磊.可满着色图和最优标号问题[D].华东师范大学.2007
[4].董伟.有关满着色的一些结果[J].商丘师范学院学报.2006
[5].董伟,许宝刚.乘积图与正则图的满着色[J].南京师大学报(自然科学版).2004
[6].董伟.有关图的满着色[D].南京师范大学.2004