论文部分内容阅读
图的平衡着色问题是Meyer[36]于1973年提出并进行研究,目前该主题已经获得了广泛的关注和研究.如果f是从V(G)到{1,2,...,t}的一个映射,那么f是图G中的t-着色.令Vi={v|f(v)=i}(1≤i≤t).如果对于所有的i和j有||Vi||Vj||≤1,那么图G的t-着色f是平衡的.最近,Wu等人[42]提出了平衡(t,k)-树-着色的概念,这一概念可以看作是真平衡t-着色的一个推广.如果G[Vi](1≤i≤t)的每个分支是最大度不超过k的树,那么这个t-着色f是图G的一个(t,k)-树-着色.一个平衡的(t,k)-树-着色是一个(t,k)-树-着色并且是平衡的.图G的平衡顶点k-荫度,记作vak=(G),是使得图G有平衡的(t,k)-树-着色的最小的整数t.图G的强平衡顶点k-荫度,记作vak≡(G),是使得图G对于每个大于等于t的t′均有平衡的(t′,k)-树-着色的最小的整数t.Wu等人[42]研究了完全等部二部图的强平衡顶点k-荫度.他们给出了va1≡(Kn,n)和va∞≡(Kn,n)的上界.同时,他们证明当n≡2(mod3)时,va1≡(Kn,n)达到了上界.随后,Tao等人[40]对当n≡0(mod3)和n≡1(mod3)时,va1≡(Kn,n)进行了研究.他们改进了其上界,并且对于一些特殊情形,获得了精确值.在本文中,进一步研究图的强平衡顶点荫度问题.本文的主要研究结果包括以下几个方面: 1.研究了完全非等部二部图Kn,n+1的强平衡顶点1-荫度和完全非等部二部图Kn,n+x(1≤x≤n)的强平衡顶点2-荫度.对于va1≡(Kn,n+1)(n≥1),给出其上界.接着,分别对n≡0,1,2(mod3)的所有情形进行了讨论.当n≡1(mod3)时,证明va1≡(Kn,n+1)达到其上界.当n≡0,2(mod3)时,令n=3k+i(i=0,2),又分四种子情形:k≡0,1,2,3(mod4)分别对其进行讨论并改进了它的上界.对于va2≡(Kn,n+x)(1≤x≤n),给出了一个紧的上界.并且证明了当n=3t(t≤2)时,va2≡(Kn,n+1)达到了其上界. 2.研究了完全三部图Kn,n,n的强平衡顶点2-荫度和强平衡顶点3-荫度.对于va2≡(Kn,n,n),当n≡1,2,3(mod4)时,分别获得了其精确值.当n≡0(mod4)时,令n=4k,再分五种子情形:k≡0,1,2,3,4(mod5)分别对其进行讨论.对于k≡1,2,3,4(mod5)的情形,分别获得了其精确值.当k≡0(mod5)时,给出其上界.对于va3≡(Kn,n,n)(n≥3),首先给出其上界.当n≡0,1,2(mod4)时,令n=4k+i(i=0,1,2),又分五种子情形:k≡0,1,2,3,4(mod5)分别对其进行讨论.当n≡0(mod4)且k≡1,2,3,4(mod5)时,分别获得了其精确值. 对k≡0(mod5)时,改进了其上界.当n≡1(mod4)且k≡2,3,4,0(mod5)时,分别获得了其精确值.对k≡1(mod5)时,改进了其上界.当n≡2(mod4)且k≡3,4,0,1(mod5)时,分别获得其精确值.对k≡2(mod5)时,改进了其上界.当n≡3(mod4),直接获得了va3≡(Kn,n,n)的一个紧的上界. 3.研究了一般图的强平衡顶点k-荫度问题.对于一般图,给出了n个顶点的简单图的强平衡顶点k-荫度的界:1≤vak≡(G)≤n/2,并且分别对达到vak≡(G)=1,vak≡(G)=n2及vak≡(G)=n2-1的图进行了等价刻画.同时,也获得了关于一般图的强平衡顶点k-荫度的Nordhaus-Gaddum类型结果. 4.研究了关于C artesian积网络的强平衡顶点k-荫度问题.同时,也讨论了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度.首先,讨论了特殊图类Cn,Pn和P etersen图H P3的强平衡顶点k-荫度.其次,对一般图的C artesian积网络,获得了其强平衡顶点k-荫度的上下界.接着,对于Cartesian积网络Pn×Pm(m≥n≥2),Cn×Cm(m≥n≥3),Kn×Km(m,n≥3)和超Petersen网络HP4讨论了其强平衡顶点k-荫度.最后,获得了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度的精确值.