论文部分内容阅读
1990年,F.Harary提出了和图的概念.令N表示正整数集,N的非空有限子集S的和图G+(S)是指图(S,E),其中uv∈E当且仅当u+v∈S.一个图G称为和图,若它同构于某个SN的和图,此时我们说S给出了G的一个和标号.图G的和数σ(G)_是使得G∪nK,是和图的非负整数n的最小值.
1994年,F.Harary[2]把和图、和数定义中的正整数集N换成整数集Z,又提出了整和图、整和数的概念.
模和图的概念是由Boland等人[3]提出的.模和图是取SZm{0}且所有算术运算均取模m(≥|S|+1)的和图,其中Zm={0,1,2,…,m-1}.一个图G的模和数ρ(G)是使得G∪ρK1是模和图的孤立点数ρ的最小值.这个概念是Sutton等人[4]提出来的.
从实用的观点来看,各种和图标号均可用作图的压缩表示,即表示图的数据结构.当利用图的压缩表示来工作时,数据压缩不仅可以节省内存,还可以加快某些图算法的运算速度.
本文的第一章主要介绍了文章中所涉及的一些概念、术语和符号.芭蕉扇Tn指在扇Fn=Pn∨K1的轴K1上悬挂一条边所得图,伞Jn指在轮Wn=Cn∨K1的轴K1上悬挂一条边所得图.在第二章和第三章中,我们分别研究了Tn、Jn及其细分图的和数、整和数、模和数及模整和数.在第四章中,确定了连圈Cn×K2细分图Gn*的整和数的界、灯笼、残灯笼的和数,并证明了风车是整和图,而对梯子Ln=Pn×K2,KL3是模和图.
在本文中,主要得到如下定理:定理2.1.1当n≥3时,ρ(Tn)=1.定理2.2.1Tn(n≥3)是整和图,也是模整和图.
定理2.2.2σ(Tn)≤{2,n=4,3,n=3或n≥6且为偶数,4,n≥5且为奇数.定理2.3.1T2*是模和图,且σ(Tn*){=1n=2、3,≤2,n≥4.定理3.1.1当n≥6且为偶数时,ρ(Jn)=1.定理3.2.1伞Jn(n≠3)是整和图,因而也是模整和图.定理3.2.2当n≥2时,σ(Jn*)≤2.定理4.1.1当n≥2时,ζ(Gn*)≤5.定理4.2.1kL3(k≥2)是模和图,因而也是模整和图.定理4.2.2当n≥3时,σ(Ln*)=2或3.定理4.3.1风车Wn*(n≥2)是整和图,因而也是模整和图.定理4.4.1灯笼Bn(n≥2)是整和图、模和图,因而也是模整和图.定理4.4.2残灯笼Bn*(n≥3)的和数为1.