賈慧羨，左大偉

(1.石家莊郵電職業(yè)技術(shù)學(xué)院基礎(chǔ)部,河北 石家莊 050021;2.石家莊鐵道大學(xué)數(shù)理系,河北 石家莊 050043)

與扇圖相關(guān)的2類圖的超邊優(yōu)美標(biāo)號(hào)*

賈慧羨1，左大偉2

(1.石家莊郵電職業(yè)技術(shù)學(xué)院基礎(chǔ)部,河北 石家莊 050021;2.石家莊鐵道大學(xué)數(shù)理系,河北 石家莊 050043)

利用遞歸方法構(gòu)造了扇圖和圖K1×2Pn的超邊優(yōu)美標(biāo)號(hào),證明了這2類圖是超邊優(yōu)美圖.

超邊優(yōu)美；扇圖Fn+1；圖K1×2Pn；圖分解；輪輻標(biāo)號(hào)；路標(biāo)號(hào)

1985年,S.P.Lo[1]首次提出邊優(yōu)美圖的概念,并給出邊優(yōu)美圖的必要條件.關(guān)于圖的邊優(yōu)美性,S.M.Lee[2]提出一個(gè)猜想:所有奇數(shù)階的樹都是邊優(yōu)美的.有關(guān)圖的邊優(yōu)美性的更多結(jié)論,可參見文獻(xiàn)[3].

1994年,J.Mitchem等[4]在討論圖的標(biāo)號(hào)問題時(shí)提出超邊優(yōu)美圖的定義.文獻(xiàn)[3]中證明了K(1,n)當(dāng)且僅當(dāng)n是偶數(shù)時(shí)是超邊優(yōu)美的,雙星圖DS(m,n)當(dāng)且僅當(dāng)m,n都是奇數(shù)時(shí)是超邊優(yōu)美的,同時(shí)他們還猜想:所有奇數(shù)階的樹都是超邊優(yōu)美的.文獻(xiàn)[5]給出了一些三正則圖是超邊優(yōu)美的.目前,超邊優(yōu)美標(biāo)號(hào)的研究還處于起步階段,研究成果非常有限.

筆者首先討論了扇圖Fn+1的超邊優(yōu)美性.文獻(xiàn)[6]中證明了n為偶數(shù)時(shí)扇圖Fn+1是超邊優(yōu)美圖,而對(duì)n為奇數(shù)的情況一直未解決.當(dāng)n(n≠3)為奇數(shù)時(shí),筆者利用遞歸構(gòu)造證明扇圖Fn+1是超邊優(yōu)美圖,當(dāng)n為偶數(shù)時(shí),用另一種方法給出證明.從而,扇圖Fn+1的超邊優(yōu)美性得到徹底解決.進(jìn)而,筆者討論了圖K1×2Pn的超邊優(yōu)美性,證明當(dāng)n>1時(shí)它是超邊優(yōu)美圖.

1 預(yù)備知識(shí)

定義1 令

稱(p,q)-圖G是超邊優(yōu)美圖.若存在一個(gè)雙射f:E→Q,使得它的導(dǎo)出映射f+:V→P,u也是一個(gè)雙射,則f稱為圖G的超邊優(yōu)美標(biāo)號(hào),集合P和Q相應(yīng)稱為圖G的頂點(diǎn)值集和邊標(biāo)號(hào)集.

定義2Pn=v1v2...vn是頂點(diǎn)個(gè)數(shù)為n且長(zhǎng)度為(n-1)的一條路,由路Pn的每一個(gè)頂點(diǎn)與同一個(gè)不在Pn上的頂點(diǎn)v0相連接,得到的圖Pn+{v0v1,v0v2,...,v0vn}為扇形圖,簡(jiǎn)記為Fn+1.它有(n+1)個(gè)頂點(diǎn)(v0,v1,...,vn),同時(shí)包含(2n-1)條邊,其中v0與vi相鄰(1≤i≤n),vi與vi+1相鄰(1≤i≤n-1).此圖中,頂點(diǎn)v0稱為中心,v0vi(1≤i≤n)稱為輪輻.

令a,m是整數(shù),m>0,方便起見,采用如下記號(hào)：

[a,a+m]={a,a+1,a+2,...,a+m-1,a+m}，

[a,a+2m]2={a,a+2,a+4,...,a+2m-2,a+2m}.

2 扇圖Fn+1的超邊優(yōu)美標(biāo)號(hào)的構(gòu)造

扇圖Fn+1包含(n+1)個(gè)頂點(diǎn)和(2n-1)條邊.易見,頂點(diǎn)數(shù)的奇偶性由n的奇偶性確定,邊數(shù)為奇數(shù),故定義1中的

Q={-(n-1),...,-1,0,1,...,n-1}.

因?yàn)閚的奇偶性不同，所以文中分2種情況討論:

現(xiàn)在的任務(wù)是定義一個(gè)雙射f:E(Fn+1)→Q,使得它的導(dǎo)出映射f+:V(Fn+1)→P,u也是一個(gè)雙射.

定理1 當(dāng)n是正偶數(shù)時(shí),扇圖Fn+1是超邊優(yōu)美圖.

證明令輪輻標(biāo)號(hào)為f(v0vi)=i-1(1≤i≤n)，路標(biāo)號(hào)為f(vivi+1)=-i(1≤i≤n-1).

i∈[1,n],f(v0vi)的f-值恰充滿集合[0,n-1];i∈[1,n-1]，f(vivi+1)的f-值恰充滿集合[-(n-1),-1].所有邊的f-值恰充滿集合Q=[-(n-1),n-1]，故f:E(Fn+1)→Q是一個(gè)雙射.下面只需證明導(dǎo)出的各點(diǎn)的f+-值是V(Fn+1)→P的一個(gè)雙射即可.

定理2[6]F4不是超邊優(yōu)美圖.

定理3 當(dāng)n為正奇數(shù)且n≠3時(shí),扇圖Fn+1是超邊優(yōu)美圖.

證明令輪輻標(biāo)號(hào)為

路標(biāo)號(hào)為

輪輻標(biāo)號(hào)恰充滿集合[1,n-1]∪{-1},路標(biāo)號(hào)恰充滿集合[-(n-1),-2]∪{0}.所有邊的f-值恰充滿集合Q=[-(n-1),n-1]，故f:E(Fn+1)→Q是一個(gè)雙射.下面只需證明導(dǎo)出的各點(diǎn)的f+-值是V(Fn+1)→P的一個(gè)雙射即可.

所有點(diǎn)的f+-值恰充滿集合[-n+4,-1]∪{1,2,3,4} mod (n+1),而{1,2,3,4} mod (n+1)={-n,-n+1,-n+2,-n+3} mod (n+1)，故所有點(diǎn)的f+-值恰充滿集合[-n,-1] mod (n+1),[-n,-1]包含n個(gè)連續(xù)的整數(shù),模去(n+1)必為頂點(diǎn)值集P.故f+:V(Fn+1)→P是一個(gè)雙射.因此,f確是Fn+1的超邊優(yōu)美雙射.

定理4 對(duì)正整數(shù)n(n≠3),扇圖Fn+1是超邊優(yōu)美圖.

由定理1、定理2和定理3,定理4的結(jié)論成立.

3 圖K1×2Pn的超邊優(yōu)美標(biāo)號(hào)的構(gòu)造

圖K1×2Pn包含(2n+1)個(gè)頂點(diǎn)和(4n-2)條邊.易見,頂點(diǎn)數(shù)目為奇數(shù)，邊數(shù)為偶數(shù).故定義1中的

P={-n,-(n-1),...,-1,0,1,...,n-1,n},

Q={-(2n-1),...,-1,1,...,(2n-1)}.

定理5 當(dāng)n是正整數(shù)時(shí),圖K1×2Pn是超邊優(yōu)美圖.

情況1n為偶數(shù).令輪輻標(biāo)號(hào)為

路標(biāo)號(hào)為

輪輻標(biāo)號(hào)恰充滿集合[1,n-1]2∪[-(n-2),-2]∪{n},路標(biāo)號(hào)恰充滿集合[-(2n-1),-(n+1)]2∪[n+2,2n-2]2.可見,輪輻標(biāo)號(hào)和路標(biāo)號(hào)的絕對(duì)值恰充滿集合[1,2n-1].又因?yàn)榈?個(gè)扇圖的邊標(biāo)號(hào)與第1個(gè)扇圖上的邊標(biāo)號(hào)相反,所以按照上面規(guī)則和定義所得到的邊標(biāo)號(hào)恰充滿集合Q,故f:E(K1×2Pn)→Q是一個(gè)雙射.下面只需證明導(dǎo)出的各點(diǎn)的f+-值是V(K1×2Pn)→P的一個(gè)雙射即可.

首先,根據(jù)2個(gè)扇圖輪輻標(biāo)號(hào)的規(guī)則,顯然f+(v0)=0.

下面討論第1個(gè)扇圖其余各點(diǎn)導(dǎo)出的f+-值:

第1個(gè)扇圖各點(diǎn)的f+-值恰充滿集合{-n}∪[-(n-1),-1]∪[2,n-2]2,這些標(biāo)號(hào)的絕對(duì)值集合恰為[1,n],按照上面規(guī)則可知,第2個(gè)扇圖上的頂點(diǎn)(除中心v0外)標(biāo)號(hào)等于第1個(gè)扇圖定點(diǎn)標(biāo)號(hào)的相反數(shù),故所得到的頂點(diǎn)標(biāo)號(hào)恰充滿集合P,故f+:V(K1×2Pn)→P是一個(gè)雙射.因此,f確是K1×2Pn的超邊優(yōu)美雙射.

情況2n為奇數(shù).令輪輻標(biāo)號(hào)為

路標(biāo)號(hào)為

輪輻標(biāo)號(hào)恰充滿集合[1,n-2]2∪[-(n-1),-2]∪{n},路標(biāo)號(hào)恰充滿集合[-(2n-2),-(n+1)]2∪[n+2,2n-1]2.可見,輪輻標(biāo)號(hào)和路標(biāo)號(hào)的絕對(duì)值恰充滿集合[1,2n-1].又因?yàn)榈?個(gè)扇圖的邊標(biāo)號(hào)與第1個(gè)扇圖上的邊標(biāo)號(hào)相反,所以按照上面規(guī)則和定義所得到的邊標(biāo)號(hào)恰充滿集合Q,故f:E(K1×2Pn)→Q是一個(gè)雙射.與前面類似,只需證明導(dǎo)出的各點(diǎn)的f+-值是V(K1×2Pn)→P的一個(gè)雙射.

首先,根據(jù)2個(gè)扇圖輪輻標(biāo)號(hào)的規(guī)則,顯然f+(v0)=0.

第1個(gè)扇圖其余各點(diǎn)導(dǎo)出的f+-值:

第1個(gè)扇圖各點(diǎn)的f+-值恰充滿集合{-n}∪[-(n-2),-1]∪[2,n-1]2,這些標(biāo)號(hào)的絕對(duì)值集合恰為[1,n],按照上面規(guī)則可知,第2個(gè)扇圖上的頂點(diǎn)(除中心v0外)標(biāo)號(hào)等于第1個(gè)扇圖定點(diǎn)標(biāo)號(hào)的相反數(shù),所以所得到的頂點(diǎn)標(biāo)號(hào)恰充滿集合P,故f+:V(K1×2Pn)→P是一個(gè)雙射.因此,f確是K1×2Pn的超邊優(yōu)美雙射.

綜上,當(dāng)n是正整數(shù)時(shí),K1×2Pn是超邊優(yōu)美圖.

[1] LO S P.On Edge-Graceful Labelings of Graphs[J].Congressus Numerantium,1985,50:231-241.

[2] LEE S M.A Conjecture on Edge-Graceful Trees[J].Scientia,1989,3:45-47.

[3] GALLIAN J A.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics,2009,DS6(9):219.

[4] MITCHEM J,SIMOSON A.On Edge-Graceful and Super-Edge-Graceful Graphs[J].Ars Combinatoria,1994,37:97-111.

[5] SHIU W C.Super-Edge-Graceful Labelings of Some Cubic Graphs[J].Acta Mathematica Sinica,2006,6:1 621-1 628.

[6] SHIU W C,Lam P C B.Super-Edge-Graceful Labelings of Multi-Level Wheel Graphs,Fan Graphs and Actinia Graphs[J].Congressus Numerantium,2005,174:49-63.

(責(zé)任編輯 向陽潔)

Super-Edge-GracefulLabelingsofTwoKindsofGraphsAssociatedwiththeFanGraph

JIA Huixian1，ZUO Dawei2

(1.Department of Basic Sciences,Shijiazhuang Post and Telecommunication Technical College,Shijiazhuang 050021,China;2.Department of Mathematics and Physics,Shijiazhuang Tiedao University,Shijazhuang 050043,China)

The super edge-graceful labelings of the fan graphsFn+1and the graphsK1×2Pnare constructed by recursion,and it is proven that they are super edge-graceful graphs.

super edge-graceful;fan graphFn+1;graphK1×2Pn;decomposition of graph;labeling of spoke;labeling of path

1007-2985(2014)02-0006-04

2013-11-26

河北省教育廳科學(xué)研究項(xiàng)目(Z2013057)

賈慧羨(1979-),女,河北衡水人,石家莊郵電職業(yè)技術(shù)學(xué)院基礎(chǔ)部講師,碩士研究生,主要從事組合數(shù)學(xué)研究.

O157

A

10.3969/j.issn.1007-2985.2014.02.003