论文部分内容阅读
图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用.
图的标号问题的研究源自于1967年Rosa的一篇论文《Oncertainvaluationoftheverticesofagraph》.图G的顶点标号是标号f到G的顶点分配,使得对每一条边uv,推出的标号依赖于顶点标号f(u)和f(v).早在1988年,Harary介绍了和图的概念,图G(V,E)被称为和图(Sumgraph),若有个从顶点集V到正整数集合S的单射f,uv∈E当且仅当f(u)+f(v)∈S.在和图中,由于具有最大标号的那个顶点没有与之相邻的顶点,所以每一个和图都一定包含孤立点,对于一个连通图G,我们令σ(G)表示使得图G成为和图的最少孤立点的个数,称为G的和数.
在1990年,J.Boland,R.Laskar,C.Turner和J.Domke提出了模和图的概念,图G(V,E)被称为模和图(Modsumgraph),若存在一个正整数n和一个从顶点集V到{1,2,…,n-1}的单射f使得对某个顶点w,有:uv∈E当且仅当f(u)+f(v)=(modn)=f(w).显然所有的和图都是模和图,反之不成立.对于一个连通图G(V,E),如果它不是模和图,则我们用ρ(G)来表示使得G成为模和图的最少孤立点的个数,称其为G的模和数.
在1994年,Harary又进一步推广了和图的概念,允许S是全体整数集,即对于图G(V,E),如果存在有顶点集V到全体整数集Z的一个映射标号λ满足:uv∈E当且仅当λ(u)+λ(v)=λ(w),其中u,v,w∈V,则称图G为整和图(Integralsumgraph).并非所有的连通图都是整和图;对于一个连通图G,如果它不是整和图,则我们用ξ(G)来表示使得G称为整合图的最少孤立点的个数,称其为G的整和数.
本文取得的主要工作可概括如下:1.在本文第三章第二节中,证明了一类新型的模和图,,.
2.在本文第四章第二节中,利用粘合的思想方法证明了龙虾树和花树都是整和图.
3.在本文第四章第三节中,又证明了MS{mn}是整和图.