论文部分内容阅读
图论是离散数学的骨干分支,离散数学则是计算机科学技术与网络信息科学的思想基础。近年来由于计算机尤其是大型计算机的发展,使得图论在数学,物理、化学、地理、生物等基础学科上面有了应用,并且在信息科学、经济等众多科学问题中有了应用。标号问题是图论中比较重要的研究内容之一。本文主要研究了亲切标号和非正则和标号,并且取得了比较好的结果。一个有n个顶点的贝壳图H(n,n-3),是通过在顶点数为n的圈Cn上一个公共点u上增加n-3条边得到的图。令v是一个在圈Cn中与u相邻的点。Sethuramam和Selvaraju[1]猜想:当k≥1,n≥4,1≤i≤k时,有一条公共边(uv)的k-贝壳图H(ni,ni-3)是亲切的。
本文研究k-贝壳图的亲切标号时,在固定了公共边(uv)上的点的标号(对u标号0且v标号为1)之后,我们采用如下方法:首先,以每个贝壳图的顶点数对4取模的余数来分类,这样就得到了四种不同情况的贝壳图;然后在每个贝壳图中再分情形进行标号;最后,通过证明得到这种标号方法是满足亲切标号的定义的,从而证明了k-贝壳图的亲切性,成功的解决了Sethuramam和Selvaraju猜想,证明了其正确性。Baca[2]等提出了非正则和标号,同时提出了非正则和强度的概念。非正则和标号分为点非正则和标号和边非正则和标号。用tvs(G)和tes(G)分别表示它的点非正则和强度和边非正则和强度。本文主要研究了广义Petersen图P(n,k)、梯形图Ln、莫比乌斯梯形图Mn、W3n、FlowerSnark及其相关图Hn及圈和圈的交图Cm□Cn的非正则和标号,得到以下结果:tes(Ln)=n,tvs(Ln)=[n/2]+1,tes(Hn)=2n+1,tvs(Hn)=n+1,tes(Mn)=n+1,tvs(Mn)=[n/2]+1,tes(W3,n)=n/2+1,tvs(W3,n)=[n/4]+1,tes(Cm□Cn)=[(2mn+2)/3],tvs(Cm□Cn)=[(mn+4)/5],