图的sigma边染色研究.pdf

《图的sigma边染色研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号UDC图的sigma指导教师王德强学位授予单位廖申请学位级别硕士论文完成日期2011年5月答厂———◆赫IllIllllIIlllllllIlllITheSigmaEdgeChromaticNumberofaGraphAthesisSubmittedtoDalianMaritimeUniversityInpartialfulfillmentoftherequirementsforthedegreeofMasterofSciencebyLiaoWei(AppliedMathematics)ThesisSupervisor：Profe

2、ssorWangDeqiangMay，2011大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博／硕士学位论文．：图的匹鲤垒边鎏鱼硒塞：一．除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明．本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担．学位论文作者签名：医荔尘．。学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文

3、的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅．本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文．同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据库》(中国科学技术信息研究所)等数据库中，并以电子出版物形式出版发行和提供信息服务．保密的论文在解密后遵守此规定．本学位论文属于：保密口在——年解密后适用本授权书．不保密彤(请在以上方框内

4、打“4")论文作者签名：离饬导师签名：蝴日期：如ff年石7t西日中文摘要摘要近年来，很多学者致力于研究图的顶点和边的识别与区分，他们使用的很多方法都涉及了图的染色，如边可区分顶点染色、顶点可区分边染色i边权值顶点染色等．上述染色均可称为邻居可区分染色，所谓邻居可区分染色即指c是图G的顶点染色或边染色，对于任意的两个相邻的元素，与其中一个元素相关联的元素的颜色类和与另一个元素相关联的元素的颜色类不同．在这些邻居可区分染色的基础上，Chartrand等人提出了sigma染色的概念，并得到了较完善的结果．本文着重研究图的sigma边染色问题，

5、主要工作有：(1)提出了图的sigma边染色概念，研究了图的sigma边染色数和边染色数，图的sigma边染色数和边数之间的关系：①sigma边染色数与边染色数的关系：首先证明了对任意连通图G，有仃’(G)≤z’(G)．然后证明了对任意正整数a和b，若a≤6，则存在图G，使得一(G)---ap7(G)=6．②sigma边染色数与边数的关系：首先证明了G是边数为s的非平凡连通图，则对于G的任意sigma边染色而言，or’(G)≠g一1．然后证明了若毛占是任意正整数，则当k≤占≤2k时，存在边数为占的连通图G的sigma边染色数仃’(G)=

6、J

7、}当且仅当k≠z-1．．(2)提出了图的sigma边连续的概念．根据边染色数与sigma边染色数之间的关系给出了路、圈和星图的sigma边染色数，然后利用构造染色方案的方法证明了路、圈和星图是sigma边连续的．(3)根据轮图、风车图、完全万叉树、梳子和毛虫树的结构特点，利用构造染色方案的方法研究了一般轮图的sigma染色数的上界，然后研究了风车图的sigma边染色数并证明了风车图不是sigma边连续的，最后研究了完全力叉树、梳子和毛虫树的sigma边染色数并证明了它们是sigma边连续的．中文摘要关键词：sigma边染色；边染色数

8、；sigma边染色数；sigma边值；sigma边连续英文摘要ABSTRACTTherehavebeennumerousstudiesusingavarietyofmethodsforthepurposeofuniquelyidentifying(ordistinguishing)theverticesofagraphortheedgesofagraph．Manyofthesemethodshaveinvolvedgraphcoloringssuchasedge-distinguishingvertexcoloring，vertex—d

9、istinguishingedgecoloring,vertexcolodngedgeweights．Moregenerally,Allthecoloringswhichhavebeenmentioneda