学位论文 > 优秀研究生学位论文题录展示

两类图的连续边着色

作　者: 王俊梅
导　师: 王世英
学　校: 山西大学
专　业: 应用数学
关键词: 连续边着色亏度树圈图花图 m×n图
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 24次
引　用: 0次
阅　读: 论文下载

内容摘要

设G是简单图，用颜色1，2，3，…对G进行正常边着色．如果每一个顶点上表现的颜色都构成一个连续的整数集合，那么就称这个边着色是连续的．图G的亏度def（G）是粘在G上使结果图可连续边着色的悬挂边的最小数目．本文分为三章，主要研究了两类图的连续边着色．第一章对本文所用的术语、记号作了介绍．第二章第一节给出了连续边着色的几个一般结论．设G₁，G₂和S是图G的子图，且满足G=G₁∪G₂和S=G₁∩G₂，那么就称G为沿着S粘接G₁和G₂得到的图．特别地，若S=K₁且V（S）={v}，则称图G是在一个顶点v上粘接G₁和G₂得到的，记作G=G₁∨_vG₂．树圈图是每条边至多属于一个圈的连通图．特殊地，称由若干个圈在同一个顶点粘接得到的树圈图为花图．第二章第二节主要研究了树圈图的连续边着色，得到了以下结果：定理2．2．7设G是一个花图，则定理2．2．9设G=G₁∨_wG₂，其中G₁，G₂是花图，则定理2．2．10设G是由若干个圈粘接得到的树圈图．若ε（G）为奇数，则def（G）≥1．定理2．2．11设G是由在一个奇圈的每个顶点上粘接一个奇圈得到的树圈图，则def（G）=1．定理2．2．12设G是在一个奇圈除一个顶点外的每个顶点上粘接一个奇圈得到的树圈图，则def（G）=1．设P₁，P₂，…，P_m是从上到下依次排列的m（m≥4）条长为n-1（n≥3）的路，第i条路上的顶点依次为v_i1，v_i2，…，v_in（1≤i≤m），则称连结顶点v_ij与v_i+1,j,v_i+3,j+2（1≤j≤n）得到的图为m×n图（如图1）．第三章证明了方格图是可连续边着色的．

全文目录

中文摘要  6-7
英文摘要  7-8
引言  8-9
第一章预备知识  9-13
  §1.1 图论的有关术语、符号  9-11
  §1.2 图的连续边着色的有关概念和符号  11-13
第二章树圈图的连续边着色  13-28
  §2.1 相关结果  13-14
  §2.2 主要结果  14-28
第三章 m×n图的连续边着色  28-30
  3.1主要结论  28-30
结束语  30-31
参考文献  31-32
发表文章目录  32-33
致谢  33-34
个人简况  34-35

两类图的连续边着色

内容摘要

全文目录

相似论文