【计算机论文全套栏目提醒】:网学会员鉴于大家对计算机论文全套十分关注,论文会员在此为大家搜集整理了“若干图的等全着色及彩虹支配问题的研究 - 硕士论文”一文,供大家参考学习
大连理工大学 硕士学位论文若干图的等全着色及彩虹支配问题的研究 姓名:罗梅琴 申请学位级别:硕士 专业:计算机软件与理论 指导教师:杨元生 20081218 大连理工大学硕士学位论文 摘 要 图的等全着色是图的着色问题中的难题之一。
对图的等全着色问题的研究不仅具有 重要的理论意义,而且在安排课表、频率分配等领域有很广泛的应用。
图的彩虹支配问 题是图的支配问题中比较活跃的研究领域之一。
图的彩虹支配问题的研究在优化理论、通讯网络设计与分析、网络搜索、模式识别等许多领域有很广泛的应用,对其研究具有现实意义。
目前国内外已有结果给出对于最大度不超过3的图的等全着色数小于等于5的界,还给出路径、圈、太阳图的2.彩虹支配数的精确值,但未给出广义Petersen图尸(%2)和 P(2k+1,k)的2.彩虹支配数的精确值。
本文主要通过计算机计算及数学推理相结合的方法,研究了图的等全着色及2一彩虹支配问题。
对3.正则图如Flower snark及其相关图、Goldberg snark及其相关图、TwistedGoldberg snark及其相关图和Blanu誊a snark图的等全着色进行研究。
给出这些图的等全着色数为4. 本文还对广义Petersen图P(n,2)和P(2k+1,k)的2一彩虹支配问题进行研究。
给出对于所有的n,广义Petersen图p(n,2)的2.彩虹支配数的精确值为: , 当nmodl0=0,3,4,9, r_●● l 以2(P(n,2)) + L 当n mod l 0=1,2,5,6,7,8. ,● ●』、 ●J 锄一5锄一5 1● ●l而对于任意k≥2时,广义Petersen图P(2k-I-1,k)的2一彩虹支配数为: 4— 当kmod5=1,4, 以2(P(ak+1,七)) 叭一5眦一5“一5 4一 1, 当kmod5=0,2,3.还给出广义Petersen图尸(,z,2)的2一彩虹支配方式。
关键词:等全着色;Flower snark;Goldberg snark;Blanu茑a snark;彩虹支配;广 义Petersen图 大连理工大学硕士学位论文 Research on Equitable Total Coloring and Rainbow Domination of Some Graphs Abstract Equitable total coloring is one of the hardest problems in graph coloring.The research on equitable total coloring has not only important theoretical,but also varied applications in such fields aS schedual and timetable,channel aSsignment problem.Rainbow domination is one of hot field in domination.Research on rainbow domination has practical significance in the field of optimization,design and analysis of communication networks,network search and pattem recognition. At present several authors have shown that a graph with maximum degree not more than 3 has at most 5-equitable total coloring,and give out the exact value of 2-rainbow dominationnum