图的强平衡顶点荫度若干问题研究

发布时间：2017-08-05 08:03

  本文关键词：图的强平衡顶点荫度若干问题研究

  更多相关文章： 平衡着色 (t k)-树-着色 强平衡顶点荫度 Nordhaus-Gaddum类型结果 Cartesian积网络

【摘要】：图的平衡着色问题是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(mod 3)时,va1≡(Kn,n)达到了上界.随后,Tao等人[40]对当n≡0(mod 3)和n≡1(mod 3)时,va1≡(Kn,n)进行了研究.他们改进了其上界,并且对于一些特殊情形,获得了精确值.在本文中,进一步研究图的强平衡顶点荫度问题.本文的主要研究结果包括以下几个方面：1.研究了完全非等部二部图Kn,n+1的强平衡顶点1-荫度和完全非等部二部图Kn,n+e(1≤e≤n)的强平衡顶点2-荫度.对于va1≡(Kn,n+1)(n≥1),给出其上界.接着,分别对n≡0,1,2(mod 3)的所有情形进行了讨论.当n≡1 (mod 3)时,证明ua1≡(Kn,n+1)达到其上界.当n≡0,2(mod 3)时,令n≡3k+i(i=0,2),又分四种子情形k≡0,1,2,3(mod 4)分别对其进行讨论并改进了它的上界.对于va2≡(Kn,n+e)(1≤e≤n),给出了一个紧的上界.并且证明了当n=3t(t≤2)时,va2≡(Kn,n+1)达到了其上界.2.研究了完全三部图Kn,n,n的强平衡顶点2-荫度和强平衡顶点3-荫度.对于va2≡(Kn,n,n),当n≡1,2,3(mod 4)时,分别获得了其精确值.当n≡0 (mod 4)时,令n=4k,再分五种子情形：k≡0,1,2,3,4 (mod 5)分别对其进行讨论.对于k≡1,2,3,4(mod 5)的情形,分别获得了其精确值.当k≡0(mod 5)时,给出其上界.对于va3≡(Kn,n,n)(n≥3),首先给出其上界.当n≡0,1,2(mod 4)时,令n≡4k+i(i=0,1,2),又分五种子情形：k≡0,1,2,3,4(mod 5)分别对其进行讨论.当n≡0(mod 4)且k≡1,2,3,4(mod 5)时,分别获得了其精确值.对k≡0(mod 5)时,改进了其上界.当n≡1(mod 4)且k≡2,3,4,0(mod 5)时,分别获得了其精确值.对k≡1(mod 5)时,改进了其上界.当n≡2(mod 4)且k≡3,4,0,1(mod 5)时,分别获得其精确值.对k≡2(mod 5)时,改进了其上界.当n≡3(mod 4),直接获得了va3≡(Kn,n,n)的一个紧的上界.3.研究了一般图的强平衡顶点k-荫度问题.对于一般图,给出了n个顶点的简单图的强平衡顶点k-荫度的界1≤vak≡(G)≤[n/2],并且分别对达到vak≡(G)=1,cak≡(G)=[n/2]及vak≡(G)=[n/2]-1的图进行了等价刻画.同时,也获得了关于一般图的强平衡顶点k-荫度的Nordhaus-Gaddum类型结果.4.研究了关于Cartesian积网络的强平衡顶点k-荫度问题.同时,也讨论了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度.首先,讨论了特殊图类Cn,Pn和Petersen图HP3的强平衡顶点k-荫度.其次,对一般图的Cartesian积网络,获得了其强平衡顶点k-荫度的上下界.接着,对于Cartesian积网络Pn口pm(m≥ n≥2),Gn口Cm(m≥n≥3),Kn□Km(m,n≥3)和超Petersen网络HP4讨论了其强平衡顶点k-荫度.最后,获得了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度的精确值.
【关键词】：平衡着色 (t k)-树-着色 强平衡顶点荫度 Nordhaus-Gaddum类型结果 Cartesian积网络
【学位授予单位】：青海师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要3-5
• 英文摘要5-10
• 第一章 绪论10-16
• § 1.1 引言10-11
• § 1.2 基本概念及术语11-12
• § 1.3 关于图的顶点荫度的研究进展12-13
• § 1.4 本文的主要研究结果13-15
• § 1.5 本论文的结构15-16
• 第二章 完全二部图的强平衡顶点荫度16-24
• § 2.1 K_(n,n+1)的强平衡顶点1-荫度16-21
• § 2.2 K_(n,n+(?))的强平衡顶点2-荫度21-24
• 第三章 完全等部三部图的强平衡顶点荫度24-54
• § 3.1 K_(n,n,n)的强平衡顶点2-荫度24-33
• § 3.2 K_(n,n,n)的强平衡顶点3-荫度33-54
• 第四章 一般图的强平衡顶点荫度54-62
• § 4.1 给定强平衡顶点k-荫度的图类54-59
• § 4.2 Nordhaus ? Gaddum类型问题59-62
• 第五章 Cartesian积网络的强平衡顶点荫度62-73
• § 5.1 关于特殊图类的强平衡顶点k-荫度63-65
• § 5.2 Cartesian积网络的强平衡顶点k-荫度65-73
• 第六章 总结及进一步研究的问题73-77
• § 6.1 总结73-75
• § 6.2 进一步研究的问题75-77
• 参考文献77-80
• 致谢80-81
• 个人简介81
• 学习经历81
• 研究成果81-82

，

本文编号：623822