几类特殊图的平衡分解问题

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:peterqiu123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的分解问题是图论研究中的一个热点问题。在2008年,Fujita和Nakami-gawa[12]提出了平衡分解以及平衡分解数的概念.设R和B分别是图G的顶点集的两个子集,并且满足R∩ B=φ,∣R∣=∣B∣。将R中的点染红色B中的点染蓝色,剩下的点不染色,这称为一个平衡点染色,若(R,B)是图G的一个平衡点染色,U是V(G)的任一子集,如果U的导出子图是连通的且∣U∩ R∣=∣U∩ B∣,称U是(R,B)的一个平衡子集。若(R,B)是图G的一个平衡点染色,那么图G的平衡分解实际上是V(G)的一个分解,即V(G)=V1∪V2∪…∪ Vr(1≤r≤n),其中Vi∩Vj=φ,并且每一个Vi都是一个平衡子集。这里,平衡分解的大小记为max{∣Vi∣:1≤i≤r}。若对于图G的任意一个k阶平衡点染色都存在一个大小至多是s的平衡分解,那么满足条件的最小整数S记为f(k,G)。另外,图G的平衡分解数记作f(G)=max{f(k,G):0≤k≤[n/2])。  在文献[12]中,Fujita和Nakamigawa等人讨论了完全二部图,树,圈等一些基本图形的平衡分解问题。设图G是n阶连通图(n≥2),Fujita和Nakamigawa证明了f(1,G)=d+1,这里d=diam(G);f(G)=2当且仅当G是一个完全图。同时,当G是n阶2-连通图时,他们证明了f(2,G)≤[n/2]+1,若n>6,则有,(3,G)≤[n/2]+1。进一步地,他们猜想,(G)≤[n/m]+1。  图的平衡分解是一种与点染色相关的分解问题,本文共有四章内容,主要是研究几类特殊图的平衡分解数问题。第一章给出了文章用到的相关符号,基本概念以及已有的结论,在第二章中,证明了一类单圈图的平衡分解问题,若G一个n阶包含n-1阶圈的连通单圈图,则[n/2]+1≤f([n/2],G)≤[n+1/2]+2。在第三章中分别研究了几类特殊图的平衡分解问题。若Qn是一个n-维超立方体图,则f(2,Qn)=n,(3,Qn)≤n+1,f(Q3)=4;若G是Petersen图,则(G)=4;若Wn是一个n阶轮图,则[n/3]+1≤f(Wn)≤[n/2]+1。文章的最后,给出了一些可以进一步探讨的问题。
其他文献
用λG表示将图G的每条边重复λ次后得到的多重图.设X是含有umn个点的集合,且它被划分为一些m-子集Xij,其中0≤i≤u-1,0≤j≤n-1。设图H的顶点集为X,边集合为E,满足对任意两个不同
随着社会科学技术的发展,医疗水平日新月异.层出不穷的诊断手法为疾病治疗提供了更加准确的信息,越来越多由基因引起的疾病被人们所发现,这就使得人们对基因疾病的研究愈加重
连锁分析是遗传制图及基因定位的重要方法之一,其通过对基因数据的分析,在基因组内去寻找被关注的基因的位置.基因定位本质上是对于基因组内的给定的遗传标记,利用统计方法确定关
随着现代化通信网络的飞速发展,离散时间排队论的研究得到了越来越多的关注.在实际生活中,我们可以发现许多有关离散时间排队的应用.经典的例子有宽带综合服务数字网络(B-ISDN)
在大多数实际的点着色问题中,对某些确定的点所着颜色都有一些限制,因此,研究点的列表着色对解决实际问题有一些重要的意义。   对于某个确定的图G,∣V(G)∣=n,且G为s列表可着
近几年来,我国的风力发电产业快速发展,在2015年,我国的风电设备装机量更是一举成为世界第一。甘肃省地处西北重要的位置,尤其是河西一带有着地势平坦开阔的戈壁滩,适宜建设大型风电场。但是由于西北特殊气候的影响,风沙等自然环境对于风力发电机的硬件要求的复杂度在不断增加,因此,对于甘肃省的风力发电机组系统模型的设计水平和制造能力提出了更高的要求。正确地建立风力发电传动系统并分析影响机组正常运行的因素及运
学位