论文部分内容阅读
图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用.
本文主要研究图的标号问题,图的标号问题起始于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集的映射.而根据对映射的不同的要求,产生了各种各样的图的标号问题.1988年,F.Harary给出(整)和图的标号;1990年,Bolland,Laskar,Yurner和Domke把和图推广到模和图.2000年,Sonntag和Teichert把(整)和图的概念推广到超图上.
和图标号在射电天文学及计算机网络理论中有着广泛的应用.本文研究了三类标号:(整)和图标号、模和图标号、(整)和超图标号.分别解决了三类标号中的一些问题和猜想.主要工作概括如下:
给出完全三部图K1,1,rr≥3的(整)和数、完全三部图K1,r,rr≥2(整)和数的一个上下界;并证明了扇图Fn及任意个扇图在中心处相交构成的图是整和图,同时荷兰风车Dn也是和图、整和图、模和图.Chen[6]猜想树是整和图,本文证明了花树是整和图;用粘合法推广了一类整和图(任意一个整和图和三叉树的沾合);给出单位图(σ(G)=1)和星图的并,任意星图的并是整和图.
Sutton,Miller,Ryan和Slamin[24]中提出了两个问题:扇图(Fn)和Kn,n的模和数.本文证明了扇图(Fn)不是模和图,并给出当n偶数时,ρ(Fn)=2;ρ(Kn,n)=n.Sonntag和Teichert[33]猜想:当d≤n-2时,ζ(()dn)=σ(()dn).本文证明了当n≥2d+1时,ζ(()dn)=σ(()dn).当d≥4时,给出了d-正则超圈是超整和图.把模和图推广到超图上去,并证明了当d≥4时,d-正则超树,d-正则超圈是超模和图.给出完全d-正则超图(()dn),当d=n,n-1,()dn是模和超图,当n≥2d+d不是模和超图.