石端銀, 徐 晶, 叢凌博

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

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

石端銀, 徐 晶, 叢凌博

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

為進一步完善整和圖理論,采用順序標號法給出龍蝦樹的一種整和標號。利用粘合的方法證明了有公共頂點的一系列多重龍蝦樹也是整和圖。該結(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 兩個圖 G1=(V1,E1)和 G2=(V2,E2),假設(shè)點 r1∈V1是 G1的一個固定頂點,稱其為 G1的根,r2∈V2是 G2的根,令 (G,r)=(G1,r1)∞(G2,r2)表示圖 G的根 r,且點 r是由 r1和 r2粘合得到的,若不強調(diào) r是圖 G的根,則可以簡記 G=(G1,r1)∞(G2,r2);其中∞是粘合符號;顯然 G的頂點集 V=(V1-{r1})∪(V2-{r2})∪{r},G的邊集 E=E1∪E2。

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

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

2 主要結(jié)果

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

(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)是整和圖。

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

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

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

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

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

(3)對于每個 k∈{1,2,…,n},由 Ak={a1,a2,…,ak}的導出子圖是 T的子龍蝦樹;序列 V={a1,a2,…,an}可以參照圖 1所示。

圖 1 龍蝦樹Fig.1 Lobster tree

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

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

由引理 2可知標號φ是 T的一種整和標號,即 T是整和圖。

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

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

3 結(jié)束語

整和圖理論研究的是圖的一種標號方法,筆者以和圖的理論為基礎(chǔ),利用順序標號法給出一般龍蝦樹的一種整和標號,從而說明龍蝦樹的整和性質(zhì)。進而用粘合的方法證明了由有限個具有一個公共頂點的龍蝦樹粘合而成的多重龍蝦樹也是整和圖。該結(jié)論進一步完善了整和圖理論,并為其他優(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].黑龍江科技學院學報,2008,18(6):478-479,482.

[6] 路永潔.關(guān)于一類新的整和圖[J].大連理工大學學報,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

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

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