和图与整和图

论文摘要

从实用的观点来看,和图标号可用作图的压缩表示,即表示图的结构.当利用输入图的压缩表示来工作时,数据压缩不仅可以节省内存,还可以加快某些图算法的运算速度.和图的概念是F.Harary 1990年提出的.设G = （V （G）,E（G））是一个图,其中V （G）, E （G）分别表示G的顶点集和边集,简记为V和E .令N （Z）表示正整数（整数）集, N （Z）的非空有限子集S的和图G+ （S）是图（ S ,E）,其中uv∈E当且仅当u + v∈S.对于图G ,若存在S ? N（Z）,使得G ? G+（S）,则称图G是（整）和图.对于任意图G ,若存在最小的非负整数σ=σ（G）（ζ=ζ（G））使得G∪σ（ζ）K1为（整）和图,称此数为G的（整）和数,即:σ=σ（G ）=min{s:（?）S（?）N,使得G∪sK1≌G+（S）,其中s≥0}（ζ=ζ（G ）=min{s:（?）S（?）Z,使得G∪sK1≌G+（S）,其中s≥0}）.显然对任意的图G有ζ（G ）≤σ（G）.为了更好地理解和图与整和图的定义,许多作者又给出了（整）和标号的定义:图G的一个标号是V （G ）→N（Z）的一一映射L.如果存在图G的一个标号L满足:对V （G）中的任意两个互异顶点u和v,u v∈E（G）当且仅当存在w∈V（G）使得L （u ）+ L（v）=L（w）,则称此标号L为图G的一个（整）和标号.为了方便,在本文中,如果没有特殊说明,顶点的（整）和标号与顶点可以不加区分.自1990年Harary提出了和图的概念,开始了对和图的研究.目前对和图的研究主要是从一些特殊图类着手,确定它们的和数、整和数.迄今为止,已经知道一些简单图类的和数与整和数,如:完全图Kn,圈Cn,路Pn,二分图Km, n,轮Wn,扇Fn,酒会图[（nK2）|—]等.但是对和图整和图性质的研究却不是很多.

论文目录

• 中文摘要
• 英文摘要
• 第一章 预备知识
• 第二章 整和图的性质
• 第三章 几类图的和数
• n , n-E（ nK₂）的和数'>§3.1 K _{n , n}-E（ nK₂）的和数
• n , n 的和数'>§3.2 G _{n , n}的和数
• n , n和数的界'>§3.3 P _{n , n}和数的界
• n和数的界'>§3.4 L_n和数的界
• n , n的不可兼性'>§3.5 C _{n , n}的不可兼性
• 第四章 一类新的整和图
• 参考文献
• 攻读学位期间发表的主要学术论文
• 致谢