论文部分内容阅读
本文仅考虑有限无向简单图,所用图论符号及术语遵循文献[1].
1990年,F.Harary[2]提出了和图,和数的概念,从而开始了对和图的研究.
1994年,F.Harary[3]又介绍了整和图,整和数的概念.
令V(G)表示图G的顶点集合,|S|表示集合S中元素的个数.令N(Z)表示正整数(整数)集,N(Z)的非空有限子集S的(整)和图G+(S)是图(S,E),其中uv∈E当且仅当u+v∈S.一个图G称为(整)和图,若它同构于某个S()N(Z)的(整)和图.图G的(整)和数σ(G)((G))是使得G∪nK1是(整)和图的非负整数n的最小值.一个连通图的最小度δ是其和数的下界,能达到此下界的图称之为δ-最优的.
模和图的概念是由Boland等人[4]提出的.
模和图是取S()Zm{0}且所有算术运算均取模m(≥|S|+1)的和图.一个图G的模和数ρ(G)是使得G∪ρK1是模和图的孤立点数ρ的最小值.
2004年,李敏[5]提出下整和图的概念.用Q+表示正有理数集.Q+的非空有限子集S的下整和图G+(S)是图(S,E),其中uv∈E当且仅当「u+v」∈S.
从实用的观点来看,各种和图标号都可用作表达图的数据结构,它们比用其他的方式输入图更能节省存储空间.
到目前为止,和图方面的研究已取得许多成果,给出了很多的一般性理论.现在研究的重点主要集中在两个方面:一方面是图的和数与它的图参数、图结构方面的联系;另一方面确定一些特殊图类的(模、整、下整)和数.
在本文的第一章中,我们主要介绍了文章中所涉及的一些概念、术语和符号以及前人关于和图的一些重要研究结果;在第二章中我们给出关于(下整)和图的一些结构性结果;第三章中,我们给出路、毛虫、皇冠、完全图不交并等一些特殊图类的下整和标号.
扇Fn是具有顶点集V={c,a1,a2,…,an}和边集E={ca1,ca2,…,can,a1a2,a2a3,…,an-1an}的图(V,E),每条边cai,i=1,…,n称为一条辐.在Fn∪σ’(Fn)的一个下整和标号中,如果「c+ai」∈V(Fn),则称cai为工作辐.
将一个圈Cm的n-个拷贝粘合于同一顶点所形成的图称之为风车.记作wnm(m≥3).中心粘合点记为c,第i个圈上其余各点分别记作ai,…,aim-1,且aim=c.
毛虫是这样的一棵树,去掉其叶子顶点(即1度顶点)后为一条路.
给定图G1,G2,设G1有n个顶点,则G1⊙G2表示这样的图:取G2的n个拷贝,且将G1的第i个点与G2的第i个拷贝的每个点连边所得的图.则Cn⊙K1(n≥3)称为皇冠.
树T被称作三路树(three-pathtree),如果它由具有一个公共端点的三条路组成.当它对应的三条路分别是Pm,Pn,Pt时,这样的树记作P(m,n,t),它相应的三条路分别记作:Pm=(a1,a2,…,am),Pn=(am,b2,b3,…,bn),Pt=(am,c2,c3,…,ct)其中am为它们的公共端点.
在本文中,我们主要得到如下定理.定理2.1.1设图G1,G2不同为和图,Li是Gi∪σ(Gi)K1的和标号,若存在n∈L2,使得n与maxL1互质,则σ(G1∪G2)≤σ(G1)+σ(G2)-1.
定理2.2.1风车wnm(m≠4,5)是δ-最优的.
定理2.3.1在Fn∪σ(Fn)K1(n≥5)的一个下整和标号中,至少存在一条辐是非工作的.
定理2.4.1设三路树P(m,n,t)(m,n,t>2)存在一组下整和标号,则最大整数标号必为一度点.
定理3.1.1路是下整和图.
定理3.2.1毛虫是下整和图.
定理3.3.1皇冠的下整和数为1.
定理3.4.1完全图Kn的不交并的下整和数为1,即σ(rKn)=1(n≥3,r≥2)
推论3.4.1σ’(Kn1∪Kn2∪…∪Knr)=1,这里ni≥3,r≥2,i=1,…r.