论文部分内容阅读
该文仅讨论有限无向简单图.用N表示自然数集;N<+>表示正整数集;Z表示整数集.(整)和图的概念由F.Harary[1,2]提出.设G=(V(G),E(G))是一个图,其中V(G),E(G)分别表示G的顶点集和边集,简记为V和E.对于图G=(S,E),其中S为N<+>(z)的非空有限子集,若对于S中任意互异顶点u和u,都有uu∈E当且仅当u+u∈S,则称图G为S的(整)和图,记为G<+>(S).对于图G,若 S N<+>(z),使得G≌G<+>(S),则称G为(整)和图.对于任意图G,存在最小的非负整数σ=σ(G)(ζ=ζ(G))使得G∪σ(ζ)K<,1>为(整)和图,称此数为G的(整)和数,即:σ=σ(G)=min{s: S N+,使得G ∪ sK<,1>≌G+(S),其中s≥0 }((=((G)=min{s: S z,使得G∪sK1≌G+(S),其中s≥0}).显然有ζ(G)≤σ(G).为了更好地理解和图与整和图的定义,许多作者<[3]>又给出(整)和标号的定义:图G的一个(整)标号是V(G)→N<+>(z)的一一映射L.如果存在图G的一个标号L满足:对V(G)中任意两个互异顶点u和v,uv∈E(G)←→ w∈V(G)使得L(u)+L(v)=L(w),则称此标号L为图G的一个(整)和标号.类似地,如果在上述和图,和数与和标号的定义中,加法运算均是在取某个模m意义下进行,并且S{1,2....,m-1}(其中m≥|V|+1且m∈N<+>),则我们就得到了模和图,模和数ρ(G)与模和标号的概念.为了方便,在该文中,如果没有特殊说明,顶点的(整,模)和标号与顶点可以不加区别.经过许多作者的研究,目前已确定一些简单图类的和数与整和数,如:圈C<,n><[1][4]>,轮W<,n><[5][6]>,路P<,n><[1]>,扇F<,n><[7]>,酒会图￣(nK<,2>)[8]和完全图K<,n><[9][10][6]>,特别地有:定理E<[8]>σ(￣nK<,2>)=ζ(￣nK<,2>)=4n-5(n≥2).定理G<[11]>立方体E<3>非整和图.该文第一部分确定了四类图￣C<,n>,￣W<,n>,￣P<,n>和￣F<,n>的和数与整和数,主要结果如下:定理2.1设n为大于9的自然数,则ζ(￣C<,n>)=σ(￣C<,n>)=2n-7.推论2.2设n为大于9的自然数,则ζ(￣W<,n>)=σ(￣W<,n>)=2n-8.定理3.1设n为大于10的自然数,则ζ(￣P<,n>)=σ(￣P<,n>)=2n-7.推论3.2设n为大于10的自然数,则ζ(￣F<,n>)=σ(￣F<,n>)=2n-8.在第二部分里,我们定义了一类新图:连圈图Jn=C<,n>×K<,2>(n ∈ N<+>),并且得到了以下结果:定理4.1设n为大于3的自然数,则3≤σ(Jn)≤9,n为奇数.定理4.2设n为大于3的自然数,则ζ(J<,n>)≤8,n为奇数.定理4.3设n为大于3的自然数,则ρ(J<,n>)≤7,n为奇数.定理4.4 ζ(J<,3>)=ρ(J<,3>)=4.