石端银,　张秋杰,　李文宇

(黑龙江科技学院 理学院, 哈尔滨 150027)



基于粘合的思想研究整和图

石端银,张秋杰,李文宇

(黑龙江科技学院 理学院, 哈尔滨 150027)

为了以数据的形式来存储图，引入了整和图标号理论。采用顺序标号法提供了联图和花树的一种整和标号，从而进一步利用粘合的思想方法证明了有公共顶点的一系列多重联图和多重花树仍然是整和图。该研究推广了整和图类型，进一步完善了整和图理论。

整和图； 粘合； 花树； 联图

0　引　言

文中所研究的图都是有限且无方向的简单图,所采用的表示符号及专业术语都与文献[1]相同。为了更好的研究图的理论,早在1988年Harary提出了和图概念[2],令图G=(V,E),其中,V表示图的顶点集,E表示图的边集,设φ是由图G的顶点集V到自然数集N的一个标号函数,它满足:边v1v2∈E当且仅当φ(v1)+φ(v2)=φ(v3),其中v1,v2,v3∈V,则称该图为和图。由定义可以看出和图都是非连通的,一定存在孤立点。如果图G是连通图,则它一定有非零和数。图G的和数σ(G)为使得图G变为和图所添加的最少孤立点的和数。后来,Harary又推广了和图的理论,从而导出整和图的概念,若图G的顶点可以用一个关于不同整数的标号函数λ给出,使得v1v2∈E当且仅当λ(v1)+λ(v2)=λ(v3),其中v1,v2,v3∈V,则图G称为整和图(Integral sum graph);整和图有的是连通图,有的是非连通图,这与和图不太相同。例如:阶为n的道路Pn;n≠4的圈Cn;n≠3的轮图Wn等都是整和图;另外,多重龙虾树也是整和图[3]。如果连通图不是整和图,可以求出相应的整和数;图G的整和数是指使图G成为整和图所需添加孤立点的最少个数。……