關(guān)于笛卡爾乘積圖的優(yōu)美性

劉家保,鄒婷,陸一南

(安徽新華學(xué)院公共課教學(xué)部,安徽合肥 230088)

關(guān)于笛卡爾乘積圖的優(yōu)美性

劉家保,鄒婷,陸一南

(安徽新華學(xué)院公共課教學(xué)部,安徽合肥 230088)

研究了笛卡爾乘積圖Pm×Pn×P1的優(yōu)美標(biāo)號(hào)算法,并且給出了他們都是優(yōu)美圖的證明,同時(shí)推廣了笛卡爾乘積圖Pm×Pn是優(yōu)美圖的結(jié)論.

優(yōu)美標(biāo)號(hào);優(yōu)美圖;笛卡爾乘積圖

1 引言

優(yōu)美圖是圖論中極其有趣的內(nèi)容,是一類特殊的簡(jiǎn)單無(wú)向圖.優(yōu)美圖的優(yōu)美標(biāo)號(hào)可應(yīng)用于編碼理論、通信網(wǎng)絡(luò)、射電天文學(xué)、導(dǎo)彈控制碼設(shè)計(jì)等方面,一直以來(lái)深受人們的重視,迄今,已有許多這方面的成果[14].但由于對(duì)優(yōu)美圖的研究缺一個(gè)系統(tǒng)而有力的工具,所以目前只能對(duì)一些特殊的圖類探索其優(yōu)美性.

圖的優(yōu)美標(biāo)號(hào)問(wèn)題由于其趣味性及較好的研究前景和應(yīng)用價(jià)值,其研究十分活躍[58],也有許多結(jié)果,但對(duì)于笛卡爾乘積圖的優(yōu)美標(biāo)號(hào)的研究結(jié)果很少.文獻(xiàn)[9]中研究了笛卡爾乘積圖Pm×Pn的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性.文獻(xiàn)[10]中證明了Pm×Pn是優(yōu)美的.本文研究了由笛卡爾乘積得到的圖Pm×Pn×P1的優(yōu)美性問(wèn)題,并得到了這類圖優(yōu)美標(biāo)號(hào)的算法,并給出了相應(yīng)的優(yōu)美性的證明,從而得到了這類圖是優(yōu)美圖的結(jié)論,推廣了笛卡爾乘積圖Pm×Pn是優(yōu)美圖的結(jié)論.

下面介紹一些基本的概念和符號(hào),其他未加說(shuō)明的術(shù)語(yǔ)和符號(hào)請(qǐng)參見(jiàn)文獻(xiàn)[1].

定義1.1對(duì)于一個(gè)圖G=(V,E),如果對(duì)每個(gè)頂點(diǎn)v∈V,存在一個(gè)非負(fù)整數(shù)L(v)(稱為頂點(diǎn)v的一個(gè)標(biāo)號(hào))滿足:

(1)?u,v∈V,如果u/=v,則L(u)/=L(v);

(2)max{L(v)|v∈V}=|E|;

(3)?e1,e2∈E,如果e1/=e2,則L′=|L(u)-L(v)|,e=uv;

那么稱圖G為優(yōu)美圖,L稱為圖G的一個(gè)優(yōu)美標(biāo)號(hào),L′稱為由L導(dǎo)出的邊標(biāo)號(hào)[3].

定義1.2設(shè)Pm、Pn、Pl分別是長(zhǎng)度為m、n、l的簡(jiǎn)單通路,圖Pm×Pn×Pl表示由Pm、Pn、Pl經(jīng)過(guò)笛卡爾乘積運(yùn)算得到的圖,記為Pm×Pn×Pl.

2 主要結(jié)果及證明

定理2.1當(dāng)m=l=1時(shí),對(duì)任意正整數(shù)n,圖P1×Pn×P1是優(yōu)美圖.

下面給出圖P1×Pn×P1各頂點(diǎn)的標(biāo)號(hào)遞推算法A如下:

作為例子分別應(yīng)用定理2.1中算法A給出P1×P3×P1,P1×P4×P1笛卡爾乘積圖的優(yōu)美標(biāo)號(hào):

圖1 P1×P3×P1的優(yōu)美標(biāo)號(hào)

圖2 P1×P4×P1的優(yōu)美標(biāo)號(hào)

引理2.1按算法A可得,圖P1×Pn×P1中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖頂點(diǎn)集與集合{0,1,2,…,8n+4}構(gòu)成單射.

證明按算法A中的標(biāo)號(hào)算法(1)-(8)將圖中各頂點(diǎn)的標(biāo)號(hào)對(duì)應(yīng)集合A,B,C,D,E,F, G,H,分兩種情況加以具體分析討論:

情況一當(dāng)n≡0(mod 2)時(shí):

情況二當(dāng)n≡0(mod 2)時(shí):

由以上討論可知,圖P1×Pn×P1頂點(diǎn)集與集合{1,2,…,8n+4}構(gòu)成單射.

引理2.2圖P1×Pn×P1中各邊的標(biāo)號(hào)均不相同,即圖P1×Pn×P1的邊集與集合{1,2,…,8n+4}構(gòu)成一一對(duì)應(yīng).

證明由引理2.1,顯然有P1×Pn×P1圖中各邊的標(biāo)號(hào)都不超過(guò)8n+4.由算法A知,圖P1×Pn×P1的邊標(biāo)號(hào)為集合{1,2,…,8n+4},而圖P1×Pn×P1共有8n+4條邊,從而所有不同的邊有不同的標(biāo)號(hào).

綜上所述,L′是從圖P1×Pn×P1的邊集到集合{1,2,…,8n+4}的一個(gè)雙射.

由引理2.1、引理2.2和優(yōu)美圖的定義,當(dāng)m,n∈?且m=1,n≥2時(shí),圖P1×Pn×P1是優(yōu)美圖.

下面討論當(dāng)m,n∈?且m≥2,n為任意自然數(shù)時(shí)的情況.

定理2.2當(dāng)m≥2,n∈?時(shí),笛卡爾乘積圖Pm×Pn×P1是優(yōu)美圖.

證明采用數(shù)學(xué)歸納法來(lái)證明.由定理2.1,當(dāng)m=1,n為任意自然數(shù)時(shí),圖P1×Pn×P1是優(yōu)美圖.

當(dāng)m≥2,n為任意自然數(shù),設(shè)Pm-1×Pn×P1是優(yōu)美圖,Lm-1是它的優(yōu)美標(biāo)號(hào),則圖Pm×Pn×P1優(yōu)美標(biāo)號(hào)算法B:

其中i+j≡1(mod 2),i=1,2,…,n+1,j=2m+1,2m+2.

作為例子分別應(yīng)用定理2.2中算法B給出P3×P2×P1、P2×P3×P1笛卡爾乘積圖的優(yōu)美標(biāo)號(hào):

圖3 P3×P1×P1的優(yōu)美標(biāo)號(hào)

圖4 P2×P3×P1的優(yōu)美標(biāo)號(hào)

引理2.3按算法B可得,圖Pm×Pn×P1中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖Pm×Pn×P1頂點(diǎn)集與集合{0,1,2,…,12n+6}構(gòu)成單射.

證明證明類似引理2.1,此略.

引理2.4圖Pm×Pn×P1中各邊的標(biāo)號(hào)均不相同,即圖Pm×Pn×P1的邊集與集合{1,2,…,12n+6}構(gòu)成一一對(duì)應(yīng).

證明證明類似引理2.2,此略.

由引理2.3、引理2.4和優(yōu)美圖的定義,容易得到,當(dāng)Pm-1×Pn×P1是優(yōu)美圖,Lm-1是它的優(yōu)美標(biāo)號(hào),則Lm是圖Pm×Pn×P1的優(yōu)美標(biāo)號(hào).

綜合定理2.1和定理2.2,很容易得到下面的定理.

定理2.3對(duì)任意的正整數(shù)m,n,笛卡爾乘積圖Pm×Pn×P1是優(yōu)美圖.

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

笛卡爾乘積圖Pm×Pn的拓?fù)浣Y(jié)構(gòu)是二維平面中的網(wǎng)格圖,而笛卡爾乘積圖Pm×Pn×P1的拓?fù)浣Y(jié)構(gòu)是由若干個(gè)小立方體疊加堆積的的三維空間圖.文中笛卡爾乘積圖Pm×Pn×P1的優(yōu)美標(biāo)號(hào)算法及給出了他們優(yōu)美性的嚴(yán)格數(shù)學(xué)證明,從而得到了這類圖是優(yōu)美圖的結(jié)論,把笛卡爾乘積圖優(yōu)美標(biāo)號(hào)從二維推廣到三維情景,加強(qiáng)了已有文獻(xiàn)的結(jié)論.

致謝衷心感謝審稿專家及編輯部對(duì)本文提出有益的修改意見(jiàn).

[1]Gallian A.A dynam ic survey of graph labeling[J].The Electronic Journal of Combinatorics,2000,12:1-95.

[2]胡紅亮.圖Cn及其r-冠的新的優(yōu)美標(biāo)號(hào)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(3):454-457.

[3]劉家保,王林.一類優(yōu)美圖的計(jì)算機(jī)算法[J].汕頭大學(xué)學(xué)報(bào):自然科學(xué)版,2011,26(2):23-28.

[4]劉家保,王林.一類圖的邊幻和標(biāo)號(hào)及其算法[J].汕頭大學(xué)學(xué)報(bào):自然科學(xué)版,2011,26(3):29-34.

[5]陳淑貞,周俊梅.關(guān)于聯(lián)圖P1∨Pn的K-強(qiáng)優(yōu)美性[J].數(shù)學(xué)雜志,2010,30(2):357-362.

[6]劉家保,潘向峰.輪形圖和扇形圖的優(yōu)美性[J].安徽大學(xué)學(xué)報(bào):自然科學(xué)版,2009,133(4):11-13.

[7]劉家保,張季.一類新的聯(lián)圖的優(yōu)美標(biāo)號(hào)算法[J].汕頭大學(xué)學(xué)報(bào):自然科學(xué)版,2011,26(1):8-10. [8]郭文富.關(guān)于圖B(m,n,p)的優(yōu)美性[J].數(shù)學(xué)雜志,1995,15(3):345-351.

[9]嚴(yán)謙泰.積圖Pm×Pn的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].系統(tǒng)科學(xué)與數(shù)學(xué),2010,30(3):341-348.

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

The gracefu lness of Cartesian p roduct graphs

Liu Jiabao,Zou Ting,Lu Yi′nan
(Department of Commom Courses,Anhui Xinhua University,Hefei 230088,China)

In this paper,we study the graceful labeling for Cartesian p roduct graphs Pm×Pn×P1and prove that they are all gracefu l graphs.These theorem s extend the results that Cartesian product graphs Pm×Pnare graceful.

graceful labeling,gracefu l graphs,Cartesian product graphs

O157.5

A

1008-5513(2012)03-0329-04

2011-10-04.

國(guó)家自然科學(xué)基金(10901001);安徽省高等學(xué)校省級(jí)自然科學(xué)基金(K J2010B076);安徽新華學(xué)院質(zhì)量工程建設(shè)(2011tskcx07).

劉家保(1982-),碩士,講師,研究方向：圖論與組合網(wǎng)絡(luò).

2010 MSC:05C78