完全二部图的单色树划分和单色树覆盖

来源 :南开大学 | 被引量 : 0次 | 上传用户:lyre1981
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个图G=(V(G),E(G))的边染色是指从其边集合E(G)到自然数子集{1,2,…,r}上的一个满射C。如果图G有这样的一个染色C,我们就称图G是一个边染色图,或r-边染色图,并用C(e)来表示边e的颜色。给定图G中的一个顶点ν,顶点ν的色邻域CN(ν)是指集合{C(e):e与ν关联}。顶点ν的色度记为dc(ν)=|CN(ν)|。一棵树被称为单色的是指这棵树中的所有边上所染颜色都相同。   1991年,Erdos,Gyarfas和Pyber提出了边染色图的单色树划分数的概念。r-边染色图G的单色树划分数,或简称为树划分数,记作tr(G),是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个顶点不交的单色树覆盖。Erdos,Gyarfas和Pyber猜想r-边染色完全图的单色树划分数是r-1,其中r≥2,并且他们证明了r=3时猜想的正确性。猜想对于r=2的情况等价于Erdos和Rado的断言:对任意的图G,图G和图G的补图至少有一个连通。对于无限完全图,Hajnal等人证明了一个r-边染色无限完全图的单色树划分数至多是r。对于有限完全图,Haxell和Kohayakawa证明了当n≥3r4r!(1-1/r)3(1-r)logr,任意r-边染色完全图Kn含有至多r个两两不同色的单色树,并且他们的顶点集合划分了Kn的顶点集合。Haxell和Kohayakawa还证明了当n充分大时,r-边染色的完全二部图Kn,n的单色树划分数至多是2r。一般地,确定tr(G)的精确的值是很困难的。   与单色树划分数相关的一个问题是r-边染色图G的单色树覆盖数,或简称为树覆盖数,它是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个单色树(可以相交)覆盖。对于完全图,以某个点为中心的所有单色星构成了一个覆盖,所以r-边染色完全图的单色树覆盖数至多是r。Erdos,Gyarfas和pyber关于树划分数的猜想的一个弱形式是:r-边染色完全图的单色树覆盖数是r-1。   本文分为三部分,第一部分主要研究了2-边染色完全二部图的单色树划分问题,第二部分主要研究了3-边染色完全等部二部图的单色树划分问题,第三部分主要研究了2-边染色和3-边染色完全二部图的单色树覆盖问题。   第二章中我们研究了2-边染色完全二部图的单色树划分。对于2-边染色的完全多部图K(n1,n2,…,nk),Kaneko,Kano和Suzuki证明了:设n1,n2,…,nk(2≤k)是满足1≤n1≤n2≤…≤nk的整数,并且n=n1+n2+…+nk-1,m=nk,则t2(K(n1,n2,…,nk))=[m-2/2n]+2。特别地,t2(Km,n)=[m-2/2n]+2,其中1≤n≤m。金泽民等人在2006年给出了2-边染色的完全多部图的单色树划分的多项式时间算法。第二章中我们给出了2-边染色的完全二部图的单色树划分更精细的刻画,我们将2-边染色完全二部图分为几种结构,并给出每种结构的单色树划分数。我们得到如下结果。   1.如果K(A,B)是一个2-边染色完全二部图,则它是下面四种结构中的一种:(1)K(A,B)有单色支撑树,(2)K(A,B})∈M,(3)K(A,B)∈S2,(4)K(A,B)∈S1。   2.如果K(A,B)∈M,则K(A,B)的顶点集可被两个同色的单色树覆盖;如果K(A,B)∈S2,则K(A,B)的顶点集要么被一个孤立点和一个单色树覆盖,要么被两个不同色的顶点不交的单色树覆盖;如果K(A,B)∈S1,并且m=|A|>|B|=n,则K(A,B)的顶点集可被至多[m-2/2n]+2个顶点不交的单色树覆盖,并且存在边染色使K(A,B)的顶点集恰被[m-2/2n]+2个顶点不交的单色树覆盖。   第三章中我们研究了3-边染色等部完全二部图的单色树划分。我们给出了几种色度条件下的单色树划分数。设K(A,B)是一个3-边染色等部完全二部图,我们得到如下结果。   1.如果存在色度为1的顶点,则t3(K(A,B))=3。   2.如果每个顶点的色度都是2,则t3(K(A,B))=2。   3.如果每个顶点的色度都是3,则t3(K(A,B))=3。   4.如果每个顶点的色度都至少是2,并且恰有一个部有色度为3的顶点,则亡3(K(A,B))=4。   第四章中我们研究了2-边染色和3-边染色完全二部图的单色树覆盖。我们的到了如下结果:   1.2-边染色完全二部图的单色树覆盖数是2。   2.3-边染色完全二部图的单色树覆盖数是4。
其他文献
压缩感知是近年来所研究的一种关于信号传输的新的理论,信号的稀疏表示、编码测量和重构算法等构成了压缩感知理论主要的三个方面.信号的稀疏表示为压缩感知的先决条件,即满足
1940年,Turan首先将极图理论作为一个学科来研究,Paul Erdos进而推动了这一理论的发展。自此,极图理论成为图论的一个重要分支。在极图理论里,我们所感兴趣的是图的各种不变量之
机器排序和机器覆盖经常在实际运用中出现,比如在网络通信中通道分配均衡问题,大型的并行计算问题,柔性生产系统中任务排序问题,等等.这篇论文主要研究了m台平行机的复合半在线排
约束矩阵方程问题是指在满足一定约束条件下的矩阵集合中求矩阵方程的解。约束条件不同,或矩阵方程不同,则得到不同的约束矩阵方程问题。 约束矩阵方程问题在结构设计、参数
本文主要研究乘子算子T与局部可积函数所生成的多线性交换子Tb的有界性问题。 首先,证明了多线性乘子交换子Tb的Sharp函数估计,并得到了该多线性交换子的Lp(w)(1<P<∞)有界性,
为筛选利用武夷山优质种质资源,促进品种结构调整,对武夷山留兰香、向天梅、醉贵妃、胭脂柳四个单枞进行植物学性状观察及主要生化成分分析。结果表明:留兰香、向天梅、醉贵
本文主要研究特殊三角剖分下二元样条函数空间的局部基和维数问题.一,利用Wang-型加密三角剖分?W下二元五次C2样条函数空间S52(?W)的Hermite插值条件,构造出空间S 52(?W)的一
为了气化缓斜和倾斜薄煤层,可采用本文作者提出的新工艺系统,其系统的本质用图1~3说明。第一,通过垂直鼓吹排瓦斯钻孔气化煤层,其钻进成本比钻进倾斜导向钻孔低的很多。第二,
全局的学习算法是对所有的训练样本构造一个模型来预测任何一个未知点的标记,而局部学习算法旨在某个给定点的邻域中构造算法,不同的测试点可能构造不同的算法模型。在某些情况
利用组合方法给出某些数学问题简洁直观的证明是组合数学研究的热点课题。其本质就是构造组合结构,寻找适当的组合变换。在本文中,一方面,我们将这种方法应用于两个等式,即Simons