石端銀,　張秋杰,　李文宇

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

?

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

石端銀,張秋杰,李文宇

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

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

整和圖； 粘合； 花樹； 聯(lián)圖

0　引　言

文中所研究的圖都是有限且無方向的簡單圖,所采用的表示符號及專業(yè)術(shù)語都與文獻(xiàn)[1]相同。為了更好的研究圖的理論,早在1988年Harary提出了和圖概念[2],令圖G=(V,E),其中,V表示圖的頂點集,E表示圖的邊集,設(shè)φ是由圖G的頂點集V到自然數(shù)集N的一個標(biāo)號函數(shù),它滿足:邊v1v2∈E當(dāng)且僅當(dāng)φ(v1)+φ(v2)=φ(v3),其中v1,v2,v3∈V,則稱該圖為和圖。由定義可以看出和圖都是非連通的,一定存在孤立點。如果圖G是連通圖,則它一定有非零和數(shù)。圖G的和數(shù)σ(G)為使得圖G變?yōu)楹蛨D所添加的最少孤立點的和數(shù)。后來,Harary又推廣了和圖的理論,從而導(dǎo)出整和圖的概念,若圖G的頂點可以用一個關(guān)于不同整數(shù)的標(biāo)號函數(shù)λ給出,使得v1v2∈E當(dāng)且僅當(dāng)λ(v1)+λ(v2)=λ(v3),其中v1,v2,v3∈V,則圖G稱為整和圖(Integral sum graph);整和圖有的是連通圖,有的是非連通圖,這與和圖不太相同。例如:階為n的道路Pn;n≠4的圈Cn;n≠3的輪圖Wn等都是整和圖;另外,多重龍蝦樹也是整和圖[3]。如果連通圖不是整和圖,可以求出相應(yīng)的整和數(shù);圖G的整和數(shù)是指使圖G成為整和圖所需添加孤立點的最少個數(shù)。關(guān)于整和圖理論更詳盡的內(nèi)容可參考文獻(xiàn)[4-5]。

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

1　基本概念

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

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

2　聯(lián)圖的整和性

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

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

(2)φ1(x)=φ2(y)當(dāng)且僅當(dāng)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聯(lián)圖G=P1∨Pn是整和圖,其中P1=a0,Pn=a1a2…an是道路。

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

定理2聯(lián)圖G1=P1∨Pn1,G2=P1∨Pn2;按照定理1中的標(biāo)號,則G1∞G2是整和圖。

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

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

3　花樹Tn，F(xiàn)是整和圖

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

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

(2)當(dāng)V(Tn,F)≥5時,采取標(biāo)號:

按照定理3中的標(biāo)號方式,分別對圖1中的T24,F和T23,F進(jìn)行順序標(biāo)號如圖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的整和標(biāo)號

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

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

4　結(jié)束語

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

[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]. 黑龍江科技學(xué)院學(xué)報, 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]. 北京: 北京大學(xué)出版社, 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

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

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

O157.5

A