论文部分内容阅读
本文仅考虑有限无向简单图,所用图论基本术语与符号遵循文献[1].
1990年Haray[2]提出和图的概念.1994年Harary[3]提出整和图的概念.令N(Z)表示正整数(整数)集,N(Z)的非空有限子集S的(整)和图G+(S)是图(S,E),其中uv∈E当且仅当u+v∈S.—个图G称为(整)和图,若它同构于某个S()N(Z)的(整)和图,此时我们说S给出了G的一个(整)和标号,并且将顶点与其标号不加区分.G的(整)和数σ(G)(ζ(G))是使得G∪nK1是(整)和图的非负整数n的最小值.
2005年Miller等人[4]提出排斥图的概念.图G∪nK1的(整)和标号S称为排斥的(exclusive),若uv∈E(G)当且仅当u+v∈SV(G).图G的排斥(整)和数ε(G)(ζ(G)是使得G∪nK1有排斥(整)和标号的非负整数n的最小值.
2006年,李敏等人璐[5]提出下整和图的概念,令Q*表示正有理数集.Q*的非空有限子集S的下整和图G+(S)是图(S,E),其中uv∈E当且仅当[u+c]∈S.—个图G称为下整和图,若它同构于某个S()Q*的下整和图,我们说S给出G的一个下整和标号,并且顶点与其标号不加区分,下整和数σ(G)是使得G∪nK1是下整和图的非负整数n的最小值.
图G∪nK1的下整和标号S称为排斥的(exclusive),若uv∈E(G)当且仅当[u+v]∈SV(G).图G的排斥下整和数ε1(G)是使得G∪nK1有排斥下整和标号的非负整数n的最小值.
2007年窦文卿等人[8]提出模整和图的概念,模整和图是取S(){0,1,2,…,m-1),且所有算术运算均取模m(≥|S|)的和图,一个图G的模整和数ψ(G)是使得G∪nK1是模整和图的非负整数n的最小值.
从实用的观点来看,各种和图标号都可被计算机用作图的压缩表示.当利用它们来工作时,不仅可以节省内存,还可以加快某些图算法的运算速度,
在本文的第一章中,我们主要介绍了文章中所涉及的一些概念、术语、符号;在第二章中我们称图(V,E)(其中V={α1,α2,b1,b2,…,bn,c1,c2],E={α1α2,c1c2,α1b1,c1bi|i=1,2,…,n})为灯笼,称去掉悬挂点α2的图为残灯笼:称将n个K3,m个K2的各一个点粘合在一起所得的图为风车,K2的边叫其柄:称由具有一个公共端点的三条路Pm,Pn,Pl组成的图为三路树,记作P(m,n,t);称图Cn2=(V,E)(其中n≥3,V={α1,α2,…,αn,c},E={α1α2.α2α3,…,αn-1,αn,αnα1,cα2})为气球.我们给出了它们的(排斥)下整和数;第三章中,我们确定了不交完全二部图的并的排斥下整和数、两个不交完全三部图的并的排斥下整和数、Kn∪mK2的(排斥)下整和数.