下整和图与排斥下整和图

摘要

本文所用图论基本术语与符号遵循文献. 1990年Harary提出和图的概念.1994年Harary提出整和图的概念.令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的最小值. 1990年Boland等人提出模和图的概念.模和图是取S(){1，2，…，m-1}且所有算术运算均取模m(≥|S|+1)的和图.由此,2002年Sutton等人提出了模和数的概念.一个图G的模和数ρ(G)是使得G∪ρK1是模和图的非负整数ρ的最小值. 2003年Miller[6]等人提出排斥图的概念.图G∪nK1的(整)和标号S称为排斥的(exclusive)，若对每条边uv∈E(G)，u+v∈S＼V(G).图G的排斥和数ε(G)是使得G∪nK1有排斥和标号的非负整数n的最小值. 2004年窦文卿提出模整和图的概念.模整和图是取S(){0，1，2，…，m-1}且所有算术运算均取模m(≥|S|)的和图.一个图G的模整和数ψ(G)是使得G∪ψK1是模整和图的非负整数ψ的最小值. 从实用的观点来看，各种和图标号都可用作图的压缩表示，即表示图的数据结构.当利用输入图的压缩表示来工作时，数据压缩不仅可以节省内存，还可以加快某些图算法的运算速度. 本文提出如下定义： 用[x]表示不超过实数x的最大整数(称为x的下整数)，Q*表示正有理数集.Q*的非空有限子集S的下整和图G+(S)是图(S，E)，其中uv∈E当且仅当[u+v]∈S.一个图G称为下整和图，若它同构于某个S()Q*的下整和图.我们说S给出G的一个下整和标号，并且顶点与标号不加区分.下整和数σ'(G)是使得G∪nK1是下整和图的非负整数n的最小值. 如果两条边有一个公共的端点，则我们称这两条边是邻接的.在G∪σ'(G)K1的一个下整和标号中，对于一个顶点w，如果存在某条边uv，使得w=[u+v]，则称w为工作顶点.显然，工作顶点均为整数点.对于边uv，如果有[u+v]∈V(G)，则称这条边是工作的. 假设S是图G的下整和标号，且整数点均为工作顶点，则称S是图G的标准下整和标号. 图G∪nK1的下整和标号S称为排斥的(exclusive)，若对每条边uv∈E(G)，[u+v]∈S＼V(G).图G的排斥下整和数ε'(G)是使得G∪nK1有排斥下整和标号的非负整数n的最小值. 下整和标号与排斥下整和标号是图的新的压缩表示. 在本文的第一章中，我们主要介绍(下整)和图的一些概念，术语，符号；第二章给出下整和图与排斥下整和图的一些结构性质；第三章确定了几类图的下整和数与排斥下整和数，并给出确定某些图类下整和数的一种方法；第四章讨论了几类图的下整和性与排斥下整和性；第五章指出了有待研究的内容.若集合S={xi|1≤i≤n}，则令S-[S]={xi-[xi]|1≤i≤n}，且对实数k，令k[S]+S={k[xi]+xi|1≤i≤n}，S.+k={xi+k|1≤i≤n}. 我们主要得到如下结果. 定理2.5设图G=(V,E)为非空下整和图，则a)不存在点v1，v2，v3，v4满足[v1]=[v4]，[v2]=[v3]，v1v2，v3v4()E，v1v3，v2v4∈E. b)不存在点vi(1≤i≤5)，满足0＜vi-v5≤1(1≤i≤4)，[v5+v1]=[v5+v4]，v5v1,v5v4，v1v3，v2v4∈E，v1v2，v3v4()E. c)不存在点vi(1≤i≤6)，满足[vi]=k(1≤i≤3)，v1v4，v2v4，v1v5，v3v5，v2v6，v3v6∈E,v3v4，v2v5，v1v6()E.d)不存在点vi(1≤i≤6)，满足[vi]=k(1≤i≤3)，v1v4，v2v4，v2v5，v2v6，v3v6∈E，v3v4，v1v5，v3v5，v1v6()E.e)不存在点vi(1≤i≤6)，满足[vi]=k(1≤i≤3)，v1v4，v2v4，v2v5，v1v6∈E，v3v4，v1v5,v3v5，v2v6，v3v6()E.f)不存在点vi(1≤i≤6)，满足[vi]=k(1≤i≤3)，v3v4，v2v5，v1v6∈E，v1v4，v2v4，v1v5，v3v5，v2v6，v3v6()E. 定理2.6设图G为下整和图，S是G的下整和标号且max(S-[S])＜1/2，k是非负整数，则k[S]+S也是G的下整和标号. 定理2.7设图G1，G2无孤立点，Si是Gi∪σ'(Gi)K1的下整和标号，σ'(Gi)≥1，且max(Si-[Si])＜1/2，Ci是Si中的工作点集(i=1，2)，且C2中存在一点与maxC1互质，则σ'(G1∪G2)≤σ'(G1)+σ'(G2)-1. 定理2.8设图G无孤立点，S=S1∪S2为G∪σ'(G)K1的下整和标号，其中S1为G的标号集，S2为孤立点的标号集，且min(S1-[S1])≥1/2，k为非负整数，则k([S]+1)+S为G∪σ'(G)K1的下整和标号. 定理2.9对任意下整和图G，V(G)={vi|0≤i≤n-1}，若v0vi∈E(1≤i≤4)，v1v2，v3v4∈E，v1v3，v1v4，v2v4()E，则图G的工作点数大于1. 在定理2.10～2.13中我们得到下面结果： 下整和图若包含C5，C6，K2,2,2或(-P6)作为其导出子图，则工作点数大于1.3.1节主要证明mK2，Kn，Kr,s,Kn-E(Kr)，Kn∪Kr,s,K1,n,1是下整和图，Km,n,q(m，n，q≥2)的下整和数为2，C5，C5∪Kn的下整和数为1. 3.2节主要证明mK2，Kn，Kr，s，Kn∪Kr,s,Kn-E(Kr)(1≤r≤n-1)，K1,n,q的排斥下整和数为1，Km,n,q(m，n，q≥2)的排斥下整和数为2. 3.3节给出确定图类下整和数的一种方法，并以Km，n，q(m，n，q≥2)，Kr，s为例介绍了这种方法.这种方法可让我们由一类下整和图构造出无数多类下整和图，也可由一类图的下整和数确定出另一类图的下整和数的界.需要用到对称点的定义和定理3.3.1. vi，vj称为图G中的对称点，如果对图G中任意不同于vi，vj的点vk，都满足vivk∈E(G)当且仅当vjvk∈E(G). 定理3.3.1设v1，v2为图G中的两对称点,G1=G+v1v2(若v1v2∈E(G)，则G1=G)，G2=G-v1v2(若v1v2()E(G)，则G2=G)，则min(σ'(G1)，σ'(G2))≤σ'(G-v1). 4.1节讨论图Cn(n≥3)，Kn-E(mK2)(2≤2m≤n)，(-)Cn(n≥3)，Kr，s-E(mK2)(r，s≥m)，Wn(n≥3)，Fn(n≥2)，Kn-E(Pm)(n≥m)在什么条件下是下整和图.主要有下面结果： 定理4.1.1Cn(n≥3)为下整和图当且仅当n=3或4. 定理4.1.2Kn-E(mK2)(2≤2m≤n)是下整和图当且仅当m=1或2. 定理4.1.3(-Cn)(n≥3)为下整和图当且仅当n=3或4. 定理4.1.4Kr,s-E(mK2)(r，s≥m)是下整和图当且仅当m=1，2或3. 定理4.1.5Wn(n≥3)为下整和图当且仅当n=3或4. 定理4.1.6Fn(n≥2)为下整和图当且仅当n=2，3或4. 定理4.1.7Kn-E(Pm)(n≥m)为下整和图当且仅当1≤m≤5. 4.2节讨论图Fn(n≥2)，Wn(n≥3)，Kr，s-E(mK2)(r，s≥m)，Kn-E(mK2)(2≤2m≤n)，Kw-E(Pm)(n≥m)在什么条件下排斥下整和数为1.主要有下面结果： 定理4.2.1ε'(Fn)=1(n≥2)当且仅当n=2，3. 定理4.2.2ε'(Wn)=1(n≥3)当且仅当n=3. 定理4.2.3ε'(Kr，s-E(mk2))=1(r，s≥m，r，s≥2)当且仅当m=1，2. 定理4.2.4ε'(Kn-E(mK2))=1(2≤2m≤n，n≠2)当且仅当m=1或2. 定理4.2.5ε'(Kn-E(Pm))=1(n≥m，n，m不同时为1，2，3)当且仅当m=1，2，3或n=m=4，5.

目录

独创声明及学位论文版权使用授权书

第一章引言

第二章下整和图与排斥下整和图的结构性质

第三章几类图的下整和数与排斥下整和数

第四章几类图的下整和性与排斥下整和性

第五章有待进一步研究的问题

参考文献

在学期间发表的学术论文

致谢