若干图的连续边着色

作     者：闫秀琴 

作者单位：山西大学 

学位级别：硕士

导师姓名：王世英

授予年度：2008年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：边着色 连续边着色 亏度 3-圈图 笛卡尔积图 

摘      要：具有重要的实际意义和理论意义的图的连续边着色问题是图论中的热点话题之一，它在组合分析和日程安排理论上有着非常广泛的应用．连续边着色问题首先是由Asratian和Kamalian在1987年提出的，其内容为：对于简单图G用颜色1，2，3…对其边正常着色，如果每一个顶点表现的颜色构成一个连续的整数集合，那么就称这个边着色是连续的．许多图是不可连续边着色的，为了测量与连续边着色的渐进程度，我们引入了图的一个新的不变量：图的亏度．图G的亏度def(G)是指加在G上使它可连续边着色的悬挂边的最小数目．本文分为三章，主要研究了若干图的连续边着色性． 第一章我们给出了本文将用到的图论的主要术语、记号和基本概念．在第二节我们介绍了连续边着色方面的基本结论． 第二章主要研究了一些圈图的连续边着色．在这章中，根据3-圈图的结构和性质，以及连续边着色的定义，得到了几类3-圈图的亏度，解决了它们的连续边着色问题．进而推广到k-圈图，我们通过运用归纳法和反证法的思想，讨论了一种k-圈图的连续边着色及其亏度问题． 主要结论叙述如下： (1)若G是四条内部不相交的(u，v)路的并图，则 (2)令C,C,C是三个不相交的圈，P(i=1，2)是两条不相交的(V(C)，V(C))路．若G是C，C，C，P和P的并图，则def(G)=0． (3)若G是仅有一个公共顶点的n(n≥1)个圈C，C，…，C的并图，则 第三章主要是通过运用归纳法思想研究了两种笛卡尔积图P×P和C×P的连续边着色问题． 主要结论叙述如下： (1)若G是两条不相交的路P和P的笛卡尔积图，则def(G)=0． (2)令C是长为m(m≥3)的圈，P是与C不相交的一条长为n(n≥0)的路．若图G是C和P的笛卡尔积，则def(G)≤1．