论文部分内容阅读
图的标号问题是图论中的一类重要问题，它研究图的各类剖分问题，其各种问题都有广泛的应用背景．其中一个问题的理论研究背景是频道分配问题．灵敏度较高的基本频道分配问题要求相互干扰的站台获得的频道不同，干扰同一站台的频道之间不能相差太小，转化为图论问题就是要求相邻的点获得的标号不同，同一点的邻点标号要有间隔。基于此，Griggs和Yeh在1992年提出了著名的L(2,1)-标号问题；孙磊老师于2008年提出了邻域限制标号问题。 本文给出了两种可应用于图的频道分配问题的非完全邻域限制标号SN(p,q)和完全邻域限制标号TN(p,q).SN(p,q)标号要求相邻的点得到的标号不同，并且度不小于一定值p的点的邻点得到的标号至少差q，也就是说，相邻的站台得到的频道不同，并且干扰同一站台的频道数达到一定值p时，各频道之间至少差q.TN(p,q)标号不仅要求相邻的点得到的标号不同，度不小于一定值p的点的邻点得到的标号至少差q，而且要求度小于p的点的邻点得到的标号至少差1.即在SN(p,q)的标号要求的基础上，还要求干扰同一站台的频道数未达到一定值p时，各频道之间至少差1。图的染色问题也是图论领域中一个重要的部分，因此数学家们相继提出了各类染色问题，并且已深入的研究了许多经典的染色问题，如图的面染色，点染色，边染色和全染色.随着图的染色问题的不断发展，数学家们在传统的染色的基础上添加各种限制，提出了许多新的图的染色问题的分支.其中由赖洪建等人于2006年提出的条件染色就是一个新的分支。图的单射染色问题也是一类重要的染色问题，一个图的单射染色就是要求图中任意一点的邻点获得的颜色彼此不同。 本研究第一章主要介绍了文章中所涉及的一些概念，符号和术语以及图的染色问题和图的几类标号问题。第二章研究了图的SN(p,q)的标号问题和TN(p,q)的标号问题，给出了一些图的SN(p,q),的标号数和TN(p,q)的标号数。第三章第一节综述了条件染色的发展，并给出了一个新结果；第二节主要研究了几类特殊图的正常单射染色，并得到了一些结果。