石端銀,　張秋杰,　李文宇

(黑龍江科技學院 理學院, 哈爾濱 150027)

?

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

石端銀,張秋杰,李文宇

(黑龍江科技學院 理學院, 哈爾濱 150027)

為了以數據的形式來存儲圖，引入了整和圖標號理論。采用順序標號法提供了聯圖和花樹的一種整和標號，從而進一步利用粘合的思想方法證明了有公共頂點的一系列多重聯圖和多重花樹仍然是整和圖。該研究推廣了整和圖類型，進一步完善了整和圖理論。

整和圖； 粘合； 花樹； 聯圖

0　引　言

文中所研究的圖都是有限且無方向的簡單圖,所采用的表示符號及專業(yè)術語都與文獻[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變?yōu)楹蛨D所添加的最少孤立點的和數。后來,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成為整和圖所需添加孤立點的最少個數。關于整和圖理論更詳盡的內容可參考文獻[4-5]。

粘合的思想最早是由Chen Zhibo在1998年提出來的,利用這種思想可以使得一系列整和圖的證明變得更為簡便。受粘合的思想的啟發(fā),筆者利用順序標號法研究了由一個公共頂點的多重聯圖以及多重花樹是整合性。

1　基本概念

定義1[6]兩個圖G1=(V1,E1)和G2=(V2,E2),假設點r1∈V1是G1的一個固定結點,稱其為G1的根,r2∈V2是G2的根,令(G,r)=(G1,r1)∞(G2,r2)表示圖G的根為r,且點r是由r1和r2粘合而得到的,若不強調r是圖G的根,則可以簡記G=(G1,r1)∞(G2,r2);其中∞就是粘合符號;顯然G的頂點集V=(V1-{r1})∪(V2-{r2})∪{r},G的邊集E=E1∪E2。

定義2設兩個圖G1=(V1,E1)和G2=(V2,E2)不相交,在G1∪G2中,把G1中的每個頂點和G2中的每個頂點連接起來得到的圖稱為G1和G2的聯圖。

2　聯圖的整和性

引理1[8]令(Gi,ri)是帶有根ri且存在一整和標號φi(i=1,2)的圖,假設:

(1)?x∈V(Gi)-{ri},φi(x)≠0,i=1,2;

(2)φ1(x)=φ2(y)當且僅當x=r1,y=r2;

(3)對于所有不同的a,b∈V(G1),且x∈V(G2)-{r2},有φ1(a)±φ2(b)≠φ2(x);

(4)對于所有不同的x,y∈V(G2)且a∈V(G1)-{r1},有φ2(x)±φ2(y)≠φ1(a);

則G=(G1,r1)∞(G2,r2)是整和圖。

定理1聯圖G=P1∨Pn是整和圖,其中P1=a0,Pn=a1a2…an是道路。

證明下面給出G的一個整和標號l,使得l(a0)=0,l(a1)=1,l(a2)=-1,l(ai)=l(ai-2)-l(ai-1)(i≥2)。顯然G=P1∨Pn是整和圖。

定理2聯圖G1=P1∨Pn1,G2=P1∨Pn2;按照定理1中的標號,則G1∞G2是整和圖。

直接由引理1和定理2便可得到推論1。

推論1G1=P1∨Pn1,G2=P1∨Pn2,…,Gm=P1∨Pnm,則G1∞G2∞…∞Gm是整和圖。

3　花樹Tn，F是整和圖

定理3所有的花樹Tn,F都是整和圖。

證明(1)當V(Tn,F)≤4時,顯然花樹Tn,F都是整和圖;

(2)當V(Tn,F)≥5時,采取標號:

按照定理3中的標號方式,分別對圖1中的T24,F和T23,F進行順序標號如圖2所示。

則(G,r)=(G1,r1)∞(G2,r2)是整和圖。

(1)對?x∈V(G1)-{r1},有φ1(x)≠0;對?x∈V(G2)-{r2},有φ2(x)≠0;

圖1　兩類花樹

圖2　花樹T24,F和T23,F的整和標號

(4)?ai,aj∈V(G1),則

對?bk∈V(G2)-{r2};由引理1知:(G,r)=(G1,r1)∞(G2,r2)是整和圖。

4　結束語

以和圖的理論為基礎,利用順序標號法為聯圖和一般花樹分別提供了一類整和標號,證明了聯圖和花樹的整和性質?；谡澈纤枷敕椒?證明了由有限個具有一個公共頂點的多重聯圖及多重花樹都是整和圖。該結論推廣了整和圖類型,完善了整和圖標號理論,也為研究其他優(yōu)美圖的整和性質提供了一定的理論基礎。

[1]WANG HAIYING. The sum numbers and the integral sum numbers of the graphKn+1E(K1,r)[J]. Discrete Mathematics, 2010, 309(12): 4137-4143.

[2]HARARY F. Sum graphs over all the integers[J]. Discrete Mathematics, 1994, 124(1/3): 99-105.

[3]石端銀, 徐晶, 叢凌博. 用粘合的方法研究一類新的整和圖[J]. 黑龍江科技學院學報, 2010, 20(5): 403-405.

[4]FERNAU H, RYAN J F, SUGENG K A. A sum labeling for the generalised friendship graph[J]. Discrete Mathematics, 2008, 308(5/6): 734-740.

[5]PYATKIN A V.Subdivided trees are integral sum graphs[J]. Discrete Mathematics, 2008, 308(9): 1749-1750.

[6]CHEN ZHIBO. On integral sum graph[J]. Discrete Mathematics, 2008, 306(1): 19-25.

[7]馬克杰. 優(yōu)美圖[M]. 北京: 北京大學出版社, 1991.

[8]CHEN ZHIBO. Integral sum graph from identification[J]. Discrete Mathematics, 1998, 181(1): 77-90.

(編輯王冬)

Research on integral sum graph based on identification

SHIDuanyin，ZHANGQiujie，LIWenyu

(College of Sciences, Heilongjiang Institute of Science & Technology, Harbin 150027, China)

This paper introduces the theory of integral sum graph labeling in order to store the graph in the form of data. The paper provides the integral sum labeling of joined graphs and flower trees adopting order labeling method and proves that all multiple joined graphs and all multiple flower trees with the same vertex remain integral sum graphs using the idea of identification. This study fascitates a wider use of the type of integral sum graph and an improvement in the integral sum graph theory.

integral sum graph; identification; flower tree; joined graph

1671-0118(2012)06-0645-03

2012-09-11

黑龍江省教育廳科學技術研究項目(12523046)

石端銀(1980-),女,山東省菏澤人,講師,碩士,研究方向:圖論,E-mail:shiduanyin@yahoo.com.cn。

O157.5

A