论文部分内容阅读
近年来,很多学者致力于研究图的顶点和边的识别与区分,他们使用的很多方法都涉及了图的染色,如边可区分顶点染色、顶点可区分边染色i边权值顶点染色等.上述染色均可称为邻居可区分染色,所谓邻居可区分染色即指c是图G的顶点染色或边染色,对于任意的两个相邻的元素,与其中一个元素相关联的元素的颜色类和与另一个元素相关联的元素的颜色类不同.在这些邻居可区分染色的基础上,Chartrand等人提出了sigma染色的概念,并得到了较完善的结果.
本文着重研究图的sigma边染色问题,主要工作有:
(1)提出了图的sigma边染色概念,研究了图的sigma边染色数和边染色数,图的sigma边染色数和边数之间的关系:
①sigma边染色数与边染色数的关系:首先证明了对任意连通图G,有σ(G)≤x(G).然后证明了对任意正整数a和b,若a≤6,则存在图G,使得σ(G)=a,x(G)=6.
②sigma边染色数与边数的关系:首先证明了G是边数为ε的非平凡连通图,则对于G的任意sigma边染色而言,σ(G)≠ε-1.然后证明了若k,ε是任意正整数,则当k≤ε≤2k时,存在边数为ε的连通图G的sigma边染色数σ(G)=k当且仅当k≠ε-1.
(2)提出了图的sigma边连续的概念.根据边染色数与sigma边染色数之间的关系给出了路、圈和星图的sigma边染色数,然后利用构造染色方案的方法证明了路、圈和星图是sigma边连续的.
(3)根据轮图、风车图、完全n叉树、梳子和毛虫树的结构特点,利用构造染色方案的方法研究了一般轮图的sigma染色数的上界,然后研究了风车图的sigma边染色数并证明了风车图不是sigma边连续的,最后研究了完全n叉树、梳子和毛虫树的sigma边染色数并证明了它们是sigma边连续的.