石端銀, 徐 晶, 叢凌博

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

用粘合的方法研究一類新的整和圖

石端銀, 徐 晶, 叢凌博

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

為進(jìn)一步完善整和圖理論,采用順序標(biāo)號(hào)法給出龍蝦樹的一種整和標(biāo)號(hào)。利用粘合的方法證明了有公共頂點(diǎn)的一系列多重龍蝦樹也是整和圖。該結(jié)論不但推廣了整和圖類型,也為樹的理論研究提供了依據(jù)。

整和圖;粘合;龍蝦樹

Abstract:This paper is an attempt to further improve the theory of integral sum graph by introducing an integral sum labeling of the lobster tree through sequential labeling method.The paper features the method of identification to prove that a series of multiple lobster trees with the public vertex is integral sum graph.This conclusion notonly promotes the type of integral sum graph,but also provides a basis for the theoretical study of the tree.

Key words:integral sum graph;identification;lobster tree

0 引 言

1 基本概念

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

定義 2 如果在圖 T中刪去所有的懸掛點(diǎn)及與其相關(guān)聯(lián)的邊后是一條路或一個(gè)孤立點(diǎn),則稱 T為毛毛蟲樹。

定義 3 如果在圖 T中把所有的懸掛點(diǎn)及其相關(guān)聯(lián)的邊去掉后剩下的是毛毛蟲樹,則稱 T為龍蝦樹。

2 主要結(jié)果

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

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

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

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

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

引理 2[4]令 (G1,r1)是一個(gè)毛毛蟲樹,其中 r1是它的頸或頭;令 (G2,r2)是一個(gè)帶有根 r2的連通圖,且圖 G2存在一整和標(biāo)號(hào)Φ,如果滿足:

(1)對(duì)每一個(gè) x∈V(G2),有Φ(x)≠0;

定理 1T′是毛毛蟲樹,在 T′的頭部頂點(diǎn)、頸部頂點(diǎn)和其他頂點(diǎn)處分別添加一個(gè)懸掛點(diǎn)得到的一類龍蝦樹 T是整和圖。

(1)令 a2是毛毛蟲樹的頭部頂點(diǎn),在此處添加的懸掛點(diǎn)為 a1,毛毛蟲樹 T′的頸部頂點(diǎn)規(guī)定為 a3,在此處添加的懸掛點(diǎn)為 a4;

(2)對(duì)于 i=1,2,…,n-1,任意兩個(gè)連續(xù)的頂點(diǎn) ai和 ai+1間的距離 d(aiai+1)≤3;

(3)對(duì)于每個(gè) k∈{1,2,…,n},由 Ak={a1,a2,…,ak}的導(dǎo)出子圖是 T的子龍蝦樹;序列 V={a1,a2,…,an}可以參照?qǐng)D 1所示。

圖 1 龍蝦樹Fig.1 Lobster tree

顯然對(duì)于 i∈{2,3,…,n},存在唯一一個(gè)整數(shù)(頂點(diǎn))j(i)

下面證明該標(biāo)號(hào)是整和標(biāo)號(hào)。φ(a1)+φ(a2)=φ(a3),φ(a2)+φ(a3)=φ(a4),φ(a3)+φ(a4)=φ(a1),從 i=5到 i=n,利用歸納法證明,n=5時(shí),T是一棵三路樹,結(jié)論成立[6];假設(shè) n>5且結(jié)論對(duì)于n-1成立,通過歸納假設(shè),對(duì)每個(gè) i=6,7,…,n-1,有整和標(biāo)號(hào)φ,

由引理 2可知標(biāo)號(hào)φ是 T的一種整和標(biāo)號(hào),即 T是整和圖。

證明 該結(jié)論直接由引理 2和定理 1可得。

推論 2有限個(gè) (不妨設(shè) k個(gè))(G1,r1),(G2,r2),…,(Gk,rk)都是定理 1中的龍蝦樹,則 (G,r)=(G1,r1)∞(G2,r2)∞…∞(Gk,rk)也是整和圖。

3 結(jié)束語(yǔ)

整和圖理論研究的是圖的一種標(biāo)號(hào)方法,筆者以和圖的理論為基礎(chǔ),利用順序標(biāo)號(hào)法給出一般龍蝦樹的一種整和標(biāo)號(hào),從而說(shuō)明龍蝦樹的整和性質(zhì)。進(jìn)而用粘合的方法證明了由有限個(gè)具有一個(gè)公共頂點(diǎn)的龍蝦樹粘合而成的多重龍蝦樹也是整和圖。該結(jié)論進(jìn)一步完善了整和圖理論,并為其他優(yōu)美圖的整和性質(zhì)的研究提供了依據(jù)。

[1] MELN IKOV L S,PYATK IN A V.Regular integral sum graphs[J].DiscreteMathematics,2002,252(3):237-245.

[2] CHEN ZH IBO.On integral sum graph[J].Discrete Math,2006,306(1):19-25.

[3] CHEN ZHI BO.Integral sum graph from identification[J].DiscreteMathematics,1998,181(1):77-90.

[4] PVATKI N A V.Subdivided trees are integral sum graphs[J].DiscreteMathematics,2008,308(9):1 749-1 750.

[5] 石端銀,杜 紅.貝殼圖是整和圖[J].黑龍江科技學(xué)院學(xué)報(bào),2008,18(6):478-479,482.

[6] 路永潔.關(guān)于一類新的整和圖[J].大連理工大學(xué)學(xué)報(bào),2000,40(1):22-23.

(編輯 王 冬)

Research on new type of integral sum graph with method of dentification

SHI Duanyin, XU Jing, CONG L ingbo
(College of Sciences,Heilongjiang Institute of Science&Technology,Harbin 150027,China)

O157.5

A

1671-0118(2010)05-0403-03

2010-07-06

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

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