简单图的邻和可区别边染色-运筹学与控制论专业论文.docxVIP

山东大学硕士学位论文 山东大学硕士学位论文 万方数据 山东大学硕士学位论文CoNTENTS 山东大学硕士学位论文 CoNTENTS Chinese Abstract．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．】[ English Abstract．．．．．．．．．．．．．．．． ．．．． ．．．．． ．．．．． ．．．．．．III Chapter 1 Introduction．．．．．．．．．．．．．．．．．．．． ．．．．．． ． 1 §1．1 Definitions and Notations ．． ．． ．．． ．．．．． ．1 §1．2 Concepts and Main results ． ．．．．．．．．．．．．． ．2 Chapter 2 Neighbor sum distinguishing edge colorings of graphs with mxi- inum average degree smaller than警 ．．7 §2．1 Lemma ． §2．2 Properties of G ．．．．．． ．．8 §2．3 Properties of日 §2．4 Discharging method ．．． ． ． 12 Chapter 3 Neighbor snm distinguishing edge colorings of planar graphs．．．1 5 §3．1 Prove of theorem 2(1) 15 §3．2 Prove of theorem 2(2)．．． ． ．． ． ． ．． ． ．20 Bibliography ．．． ．． ．．． ．．．．．． ．．． ．．．．．．． ．．．．．．．．31 Acknowledgements．．．．．．．．．．．．．．．．．．． ．．． ．．．．．．．．．35 III 万方数据 山东大学硕士学位论文一IV— 山东大学硕士学位论文 一IV— 万方数据 山东大学硕士学位论文简单图的邻和可区别边染色 山东大学硕士学位论文 简单图的邻和可区别边染色 李红杰 (山东大学数学学院，济南，250100) (指导老师：吴建良教授) 中文摘要 对于图G=(K E)，它的正常㈨一边染色指的是G的边集E到颜色集G： f翻={1，2，¨．，露)的映射妒，若对于任意两条相互关联的边vel，e2∈E(G)有妒 (e1)≠妒(e2)，则称妒是G的正制件边染色，我们用x’(G)表示使得G有正 常M一边染色的最小整数k．给定G的正常㈨一边染色妒，(u)表示与u相邻的 边的权值和，任意UV∈E(G)，有(“)≠(t，)，称染色妒为图G的邻和可区 别的[明-边染色．我们用)(；(G)表示使得G有邻和可区别的吲一边染色的最小 整数屉．G的平均度为垒苇器产，记为ad(G)．最大平均度mad(G)是G的 子图的平均度的最大值．本文主要证明了两个定理： 定理1如果G是不含孤立边的mad(G)萼的简单图，那么)(，0(G)k，- 其中尼=max{A(a)+3，11}． 定理2(1)设G是最大度为△，围长为g的正常平面图，如果g≥5．则 x兰(G)≤k，其中后=max{A(G)+3，10}． (2)设G是最大度为△且不含4一圈的正常平面图，则x0(G)s k，其中当 A(a)≠10时，七=max{A(G)+3，13)，当zx(a)=10时，尼=max{A(G)+ 3，14)=14． 本文主要内容具体分为三章展开： 第一章，首先介绍了本文用到的基本定义和符号，其次介绍了相关概念 和已得到结果，最后给出了本文要证明的两个定理． 第二章，我们利用权转移方法证明了定理1． 第三章，我们利用欧拉原理及权转移规则构造反例证明了定理2． 关键词：正常边染色；邻和可区别的边染色；最大平均度；平均度；平面 图；权转移方法 万方数据 山东大学硕士学位论文 山东大学硕士学位论文 万方数据 Neighbor Neighbor sum distinguishing edge colorings of simple graphs Hon舀ie Li (School of Mathematics，Shandong University,Jinan 250100) (Professor：Jianliang Wu) ABSTRACT A proper㈨一edge coloring of a graph G is a mapping妒：E(C)_÷C— f纠2．[1，2， ，后)，iffor each adjacent two edges e