检索结果-南通市图书馆

新疆大学学报（自然科学版）（中英文） 2022年第1期39卷 16-18,41页

作者：程书婷吴宝音都仍新疆大学数学与系统科学学院新疆乌鲁木齐830017

令f(r,n)是使得任意r-边着色完全图K_(n)包含一个长度至少为k的单色圈的最大正整数k.2009年,Faudree,Lesniak和Schiermeyer提出猜想:任意(r+1)-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中r≥2.同时他们还证明了f(2,n)≥[2n/3... 详细信息

令f(r,n)是使得任意r-边着色完全图K_(n)包含一个长度至少为k的单色圈的最大正整数k.2009年,Faudree,Lesniak和Schiermeyer提出猜想:任意(r+1)-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中r≥2.同时他们还证明了f(2,n)≥[2n/3]且界是紧的,其中n≥6.2011年,Fujita证明了当n=2r时猜想不成立,同时还证明了任意r-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中1≤r≤n.本文中我们证明了存在(r+1)-边着色完全图K_(n)包含一个长度小于n/r的单色圈,其中n=tr+1,r≥2且n-1/r为正偶数.令c表示K_(n)的某种k-边着色.在边着色c的完全图K_(n)中,令moc(K_(n),c)表示单色树的最大阶数且moc(n,k)=min{moc(K_(n),c):c是K_(n)的某种k-边着色}.我们还证明了当n≡0,1(mod 4)时,moc(n,3)=[n/2];当n≡2,3(mod 4)时,moc(n,3)=[n+1/2],其中n≥3.

关键词：周长边着色完全图单色圈单色树

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

图的杂色树划分问题

图的杂色树划分问题

引用

作者：周淑俊浙江师范大学

学位级别：硕士

图G的r-边染色是指一个满射φ：E(G)→{1,2,…,r}.边染色图G称为单色的,若图G的所有边都染有相同的颜色.边染色图G称为杂色的,若图G的任意两条边都染有不同的颜色.Erdos的一个简单而著名的注记表明任何2-边染色完全图Kn都有一棵单色支撑... 详细信息

图G的r-边染色是指一个满射φ：E(G)→{1,2,…,r}.边染色图G称为单色的,若图G的所有边都染有相同的颜色.边染色图G称为杂色的,若图G的任意两条边都染有不同的颜色.Erdos的一个简单而著名的注记表明任何2-边染色完全图Kn都有一棵单色支撑树.一个自然的推广题是：将r-边染色完全图Kn划分成尽可能少的点不交的单色树.Erdos等人提出了r-边染色图的单色子图划分数的概念.对应于图的单色子图划分问题,Chen等人提出了r-边染色图的杂色树划分数的概念.边染色图的单色和杂色子图划分问题在图论研究中具有重要的理论意义,相关的研究日益引起众多研究者的兴趣.本文主要研究边染色图的杂色子图划分问题,主要研究结果如下：第一部分从算法的角度研究r-边染色完全二部图Km,n的杂色树划分问题,设计了一个多项式时间算法,它能在多项式时间内找到至tr(Km,n)棵点不交的杂色树覆盖Km,n的所有顶点.第二部分主要考虑r-边染色完全三部图的杂色树划分数问题,在第一部分完全二部图的结论基础上,继续研究完全三部图并得到了r-边染色完全三部图的杂色树划分数的精确表达式.

关键词：杂色树单色树覆盖边染色

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

边染色图的顶点划分问题

边染色图的顶点划分问题

引用

作者：朱培培浙江师范大学

学位级别：硕士

图的顶点划分问题一直都是图论研究的热点之一,在图论研究中具有重要的理论意义,并且在计算机科学和信息科学等多个领域具有广泛的应用.Erdos的个有名的注记表明：任何2-边染色完全图Kn都有一棵单色支撑树.Bollobas等人将如下划分... 详细信息

图的顶点划分问题一直都是图论研究的热点之一,在图论研究中具有重要的理论意义,并且在计算机科学和信息科学等多个领域具有广泛的应用.Erdos的个有名的注记表明：任何2-边染色完全图Kn都有一棵单色支撑树.Bollobas等人将如下划分问题归于Erdos的结论的一个推广问题：将r-边染色完全图Kn划分成尽可能少的顶点不交的单色树.实际上,早在上个世纪的七八十年代：研究者就对这类划分问题开展了研究.Erdos等提出了r-边染色图的单色子图划分数的问题.研究者们关于边染色图的单色树,单色圈,单色路的划分问题相继得出了不少结果.Chen等人对应地提出了r-边染色图的杂色树划分数的概念. 本文主要研究边染色图的单色树和杂色树的划分问题,共分为五章. 第一章给出了边染色图的顶点划分问题研究现状和一些基本概念. 第二章研究了一种在限制条件下的r-边染色完全多部图的单色树划分数的一个问题,并得出单色树划分数的一个确切值. 第三章定义了两种特殊边染色,利用这两种特殊边染色得到了r-边染色完全多部图的杂色树划分数的下界. 第四章主要考虑r-边染色完全多部图Kn1,n2,…,nk（k≥4）的杂色树划分数的上界的问题,并且其上界和下界最多相差1. 第五章给出了一个进一步考虑的问题,并考虑r-边染色完全多部图杂色树划分的算法问题.

关键词：单色树杂色树覆盖划分边染色

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：