论文部分内容阅读
图的分解问题是图论研究中的一个热点问题。在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。文章的最后,给出了一些可以进一步探讨的问题。