关于若干图的(t,1)-连续边染色

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:ygl360
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文讨论的图均为有限无向的简单图。图的染色问题的研究一直是图论界的热点,图的连续边染色问题也是图染色问题的热点话题之一,它具有重要的实际意义和理论意义,它在组合分析和日程安排理论上有着非常广泛的应用。连续边染色问题首先是由Asratian和Kamalian在1987年提出的:对于简单图G用颜色1,2,3,…对其边正常染色,如果与每一个顶点关联的边的颜色构成一个连续的整数集合,那么就称这个边染色是连续的或连续边染色。在本文中,所研究的是连续边染色的一种推广(t,1)-连续边染色。  第一章中主要介绍了一些基本概念,相关符号以及图的(t,1)-连续边染色的概念。  设图G(V,E)是简单无向图,α是集合E(G)到集合[t]={1,2,…,t)的一个映射。若α满足以下条件:  (1)α是图G的边可染映射;  (2)对于每一种颜色i∈[t],至少存在一边e∈E使α(e)=i;  (3)图G的任一顶点,满足  dG(v)-1≤max Sα(V)-min Sα(v)≤dG(v),其中Sα(v)={α(uv):u∈N(v),u∈V(G)}。则称图G是(t,1)-连续边可染的,α是图G的(t,1)-连续边可染映射。称wi(G)=min{t:G是(t,1)-连续边可染的},W1(G)=max{t:G是(t,1)-连续边可染的}分别为图G的最小(t,1)-连续边染色数和最大(t,1)一连续边染色数。  第二章介绍了笛卡尔积图G1×G2和直积图G1×G2的一些基本性质和(t,1)-连续边染色,给出了本文的主要定理及证明。第三章重点讨论直积图的最小(t,1)-连续边染色数W1和最大(t,1)-连续边染色数W1,并给出了相应的结论。在第四章中给出了可以进一步探讨的一些问题。
其他文献
本论文分为两个部分。第一章是预备篇,介绍一些文章所需要的Hilber流形方面的基本概念和性质。第二章的主题是C*-代数的几何表述。首先,我们对文献[1]《A functional represent
内点算法是求解线性规划的有效算法,它不仅具有多项式复杂性,实际计算性能也可以与单纯形法媲美.自1984年第一个具有实用性的多项式算法——Karmarkar算法提出以来,经过众多
生物体的表型特征受遗传效应影响,定位影响生物体表现型的性状位点,即数量性状位点(QTL)定位,在科学领域、经济领域都有重要的意义.区间定位方法被广泛应用到QTL定位中,然而,一些性
学位
世界的本质是非线性的,混沌则是非线性科学中的一朵奇葩。混沌理论研究在20世纪七八十年代得到了很大的发展。进入到了九十年代,在继续关注混沌理论研究的同时,人们开始把目光聚
设G是k-连通图,e为图G的边,图G收缩边e后所得的图记为G/e,若G/e仍为k-连通图,则称e为图G的k可收缩边,简称可收缩边.否则称为不可收缩边(.)如果k-连通图中存在可收缩边,则可使用归纳