本文主要研究内容
作者吕萧（2019）在《低最大度的平面图的(2,1)-全标号》一文中研究指出：图论最早起源于18世纪三十年代.Euler在1736年解决了柯尼斯堡七桥问题,由此图论诞生.伴随着图论的兴起和发展,这门新兴的学科,逐渐在化学、信息论、生物学、网络理论、控制论、博弈论及计算机科学领域产生了广泛的应用.图染色问题作为图论最经典的问题之一更是受到了广泛关注.由著名的四色猜想开始,先后产生了点染色、边染色、全染色、列表染色、频道染色等一系列新的研究方向,在现实生活中染色理论有着广泛的应用背景.本文所考虑的图都是连通的简单有限图.如果图G能够嵌入到平面上使得G中的边仅在端点处相交,则称G为平面图或可平面图.通常情况下,V(G),E(G)分别表示一个图G的顶点集合和边集合.|V(G)|、|E(G)|分别表示图G的顶点数和边数.如果V’ c V,E’(?)E,称G’=(V’,E’)是G=(V,E)的子图,并记作G’(?)G;我们常用添加或删除一些顶点和边的方法来构造一类新图.若V’(?)V(G),则G-V’是在G中删除V’中的点和与它们关联的所有边而得到的子图.若E’(?)E(G),则G-E是在G中删除E’中的边而得到的子图.图G中一个顶点u的度是指G中与u相关联的边的数目,记作dG(v)或d(v).用δ(G),△(G)分别记作图G的最小度和最大度.面f的度d(f)是指与面f相关联的边的数目.频道分配问题实质上是一个如何分配无线电频道资源以实现最合理应用的最优化问题.在频道分配问题中,为避免传输信号之间的干扰,若两个站点距离非常近,则它们的频率至少相差2;若两个站点稍近,则只需分配不同频率即可.受此问题的启发,Griggs和Yeh[10]引入了 L(2,1)-标号并且很快被推广到L(p,q)-标号的形式.图G的一个L(p,q)-标号是从V(G)到所有非负整数的一个映射φ,使得如果点;x和y相邻,那么|φ(x)-φ(y)|≥ p;如果点x和y距离为2,那么|φ(x)-m(y)|≥ q.图的关联图是指将图G中的每条边都用一条长为2的路代替所形成的新图.Havet[6,7]将一个图的关联图的L(p,1)-标号问题定义为图的(p,1)-全标号问题.该问题也可以被看作是全染色问题的一种推广形式.图G有一个k-(p,1)-全标号当且仅当存在一个将V(G)∪E(G)映射到颜色集合{0,1,2,...,k})的函数f满足:(1)若边uv ∈ E(G),|f(u)-f(v)|≥1;(2)若边e1和e2在G中相邻,则|f(e1)-f(e2)|≥ 1;(3)若顶点u和边e相关联,则|f(u)-f(e)| ≥ p.使得G可k-(p,1)-全标号的最小的正整数k称为是图G的(p,1)-全标号数,并记作λpT(G).Havet和Yu[8]提出了如下的(p,1)-全标号猜想:猜想1.3.3[6,8]G是一个最大度为△的平面图,则有λpT(G)≤△+2p-1或λpT(G)≤min{△+2p-1,2△+p-1}.关于图G的(p,1)-全标号数和(2,1)-全标号数的重要的研究结果如下.定理 1.3.4[1]G 是任意一个简单图,则max{r(χ(G)-1)+1,s(λ’(G)-1)+1,t+1}≤Xr,s,t(G)≤r(X(G)-1)+s(χ’(G)-1)+t+1.定理1.3.10[19]令G是一个最大度为△的可平面图,整数p满足p≥2.若G满足△ ≥ 4p+4,则有 λpT(G)≤ △+2p-2.定理1.3.13[22]若G是一个最大度△ ≥ 12的平面图,则△+l ≤ λ2T(G)≤ △+2.定理1.3.14[23]若G是一个最大度△ ≥ 9的平面图.若G中不含长为k的圈,k∈{3,4,5,6},则有 λ2T(G)≤ △+2.本文主要讨论平面图的(2,1)-全标号数.第二章是本论文的重点部分,我们给出了 △(G)=11,10,9的带有限定条件的平面图的(2,1)-全标号数及其证明.第三章我们给出了 △=8,7.6的带有限定条件的平面图的(2,1)-全标号数并且还给出了使用四色定理和不使用四色定理两种不同的证明.本文我们主要得到了如下结论:定理2.1.1若G为平面图,△(G)=11且G中3-圈不与k-圈相邻,k∈{3,4},则 λ2T(G)≤ △+2.定理2.1.2若G为平面图,△(G)=10且G中3-圈不与k-圈相邻,k ∈ {3,4},则(G)≤△+2.定理2.1.3 若G为平面图.△(G)=9且G中3-圈不与k-圈相邻,∈{3,4,5},则 λ2T(G)≤△+2.定理3.2.1 若G为平面图,△(G)=p+5且G不包含5-圈和6-圈,则λ2T(G)<△+5,p1,2,3.
Abstract
tu lun zui zao qi yuan yu 18shi ji san shi nian dai .Eulerzai 1736nian jie jue le ke ni si bao qi qiao wen ti ,you ci tu lun dan sheng .ban sui zhao tu lun de xing qi he fa zhan ,zhe men xin xing de xue ke ,zhu jian zai hua xue 、xin xi lun 、sheng wu xue 、wang lao li lun 、kong zhi lun 、bo yi lun ji ji suan ji ke xue ling yu chan sheng le an fan de ying yong .tu ran se wen ti zuo wei tu lun zui jing dian de wen ti zhi yi geng shi shou dao le an fan guan zhu .you zhe ming de si se cai xiang kai shi ,xian hou chan sheng le dian ran se 、bian ran se 、quan ran se 、lie biao ran se 、pin dao ran se deng yi ji lie xin de yan jiu fang xiang ,zai xian shi sheng huo zhong ran se li lun you zhao an fan de ying yong bei jing .ben wen suo kao lv de tu dou shi lian tong de jian chan you xian tu .ru guo tu Gneng gou qian ru dao ping mian shang shi de Gzhong de bian jin zai duan dian chu xiang jiao ,ze chen Gwei ping mian tu huo ke ping mian tu .tong chang qing kuang xia ,V(G),E(G)fen bie biao shi yi ge tu Gde ding dian ji ge he bian ji ge .|V(G)|、|E(G)|fen bie biao shi tu Gde ding dian shu he bian shu .ru guo V’ c V,E’(?)E,chen G’=(V’,E’)shi G=(V,E)de zi tu ,bing ji zuo G’(?)G;wo men chang yong tian jia huo shan chu yi xie ding dian he bian de fang fa lai gou zao yi lei xin tu .re V’(?)V(G),ze G-V’shi zai Gzhong shan chu V’zhong de dian he yu ta men guan lian de suo you bian er de dao de zi tu .re E’(?)E(G),ze G-Eshi zai Gzhong shan chu E’zhong de bian er de dao de zi tu .tu Gzhong yi ge ding dian ude du shi zhi Gzhong yu uxiang guan lian de bian de shu mu ,ji zuo dG(v)huo d(v).yong δ(G),△(G)fen bie ji zuo tu Gde zui xiao du he zui da du .mian fde du d(f)shi zhi yu mian fxiang guan lian de bian de shu mu .pin dao fen pei wen ti shi zhi shang shi yi ge ru he fen pei mo xian dian pin dao zi yuan yi shi xian zui ge li ying yong de zui you hua wen ti .zai pin dao fen pei wen ti zhong ,wei bi mian chuan shu xin hao zhi jian de gan rao ,re liang ge zhan dian ju li fei chang jin ,ze ta men de pin lv zhi shao xiang cha 2;re liang ge zhan dian shao jin ,ze zhi xu fen pei bu tong pin lv ji ke .shou ci wen ti de qi fa ,Griggshe Yeh[10]yin ru le L(2,1)-biao hao bing ju hen kuai bei tui an dao L(p,q)-biao hao de xing shi .tu Gde yi ge L(p,q)-biao hao shi cong V(G)dao suo you fei fu zheng shu de yi ge ying she φ,shi de ru guo dian ;xhe yxiang lin ,na me |φ(x)-φ(y)|≥ p;ru guo dian xhe yju li wei 2,na me |φ(x)-m(y)|≥ q.tu de guan lian tu shi zhi jiang tu Gzhong de mei tiao bian dou yong yi tiao chang wei 2de lu dai ti suo xing cheng de xin tu .Havet[6,7]jiang yi ge tu de guan lian tu de L(p,1)-biao hao wen ti ding yi wei tu de (p,1)-quan biao hao wen ti .gai wen ti ye ke yi bei kan zuo shi quan ran se wen ti de yi chong tui an xing shi .tu Gyou yi ge k-(p,1)-quan biao hao dang ju jin dang cun zai yi ge jiang V(G)∪E(G)ying she dao yan se ji ge {0,1,2,...,k})de han shu fman zu :(1)re bian uv ∈ E(G),|f(u)-f(v)|≥1;(2)re bian e1he e2zai Gzhong xiang lin ,ze |f(e1)-f(e2)|≥ 1;(3)re ding dian uhe bian exiang guan lian ,ze |f(u)-f(e)| ≥ p.shi de Gke k-(p,1)-quan biao hao de zui xiao de zheng zheng shu kchen wei shi tu Gde (p,1)-quan biao hao shu ,bing ji zuo λpT(G).Havethe Yu[8]di chu le ru xia de (p,1)-quan biao hao cai xiang :cai xiang 1.3.3[6,8]Gshi yi ge zui da du wei △de ping mian tu ,ze you λpT(G)≤△+2p-1huo λpT(G)≤min{△+2p-1,2△+p-1}.guan yu tu Gde (p,1)-quan biao hao shu he (2,1)-quan biao hao shu de chong yao de yan jiu jie guo ru xia .ding li 1.3.4[1]G shi ren yi yi ge jian chan tu ,ze max{r(χ(G)-1)+1,s(λ’(G)-1)+1,t+1}≤Xr,s,t(G)≤r(X(G)-1)+s(χ’(G)-1)+t+1.ding li 1.3.10[19]ling Gshi yi ge zui da du wei △de ke ping mian tu ,zheng shu pman zu p≥2.re Gman zu △ ≥ 4p+4,ze you λpT(G)≤ △+2p-2.ding li 1.3.13[22]re Gshi yi ge zui da du △ ≥ 12de ping mian tu ,ze △+l ≤ λ2T(G)≤ △+2.ding li 1.3.14[23]re Gshi yi ge zui da du △ ≥ 9de ping mian tu .re Gzhong bu han chang wei kde juan ,k∈{3,4,5,6},ze you λ2T(G)≤ △+2.ben wen zhu yao tao lun ping mian tu de (2,1)-quan biao hao shu .di er zhang shi ben lun wen de chong dian bu fen ,wo men gei chu le △(G)=11,10,9de dai you xian ding tiao jian de ping mian tu de (2,1)-quan biao hao shu ji ji zheng ming .di san zhang wo men gei chu le △=8,7.6de dai you xian ding tiao jian de ping mian tu de (2,1)-quan biao hao shu bing ju hai gei chu le shi yong si se ding li he bu shi yong si se ding li liang chong bu tong de zheng ming .ben wen wo men zhu yao de dao le ru xia jie lun :ding li 2.1.1re Gwei ping mian tu ,△(G)=11ju Gzhong 3-juan bu yu k-juan xiang lin ,k∈{3,4},ze λ2T(G)≤ △+2.ding li 2.1.2re Gwei ping mian tu ,△(G)=10ju Gzhong 3-juan bu yu k-juan xiang lin ,k ∈ {3,4},ze (G)≤△+2.ding li 2.1.3 re Gwei ping mian tu .△(G)=9ju Gzhong 3-juan bu yu k-juan xiang lin ,∈{3,4,5},ze λ2T(G)≤△+2.ding li 3.2.1 re Gwei ping mian tu ,△(G)=p+5ju Gbu bao han 5-juan he 6-juan ,ze λ2T(G)<△+5,p1,2,3.
论文参考文献
论文详细介绍
论文作者分别是来自山东师范大学的吕萧，发表于刊物山东师范大学2019-07-06论文，是一篇关于全标号论文,平面图论文,权转移论文,山东师范大学2019-07-06论文的文章。本文可供学术参考使用，各位学者可以免费参考阅读下载，文章观点不代表本站观点，资料来自山东师范大学2019-07-06论文网站，若本站收录的文献无意侵犯了您的著作版权，请联系我们删除。
标签：全标号论文; 平面图论文; 权转移论文; 山东师范大学2019-07-06论文;