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

賈慧羨，左大偉

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

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

賈慧羨1，左大偉2

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

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

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

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

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

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

1 預備知識

定義1 令

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

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

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

[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)美標號的構(gòu)造

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

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

因為n的奇偶性不同，所以文中分2種情況討論:

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

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

證明令輪輻標號為f(v0vi)=i-1(1≤i≤n)，路標號為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是一個雙射.下面只需證明導出的各點的f+-值是V(Fn+1)→P的一個雙射即可.

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

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

證明令輪輻標號為

路標號為

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

所有點的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)，故所有點的f+-值恰充滿集合[-n,-1] mod (n+1),[-n,-1]包含n個連續(xù)的整數(shù),模去(n+1)必為頂點值集P.故f+:V(Fn+1)→P是一個雙射.因此,f確是Fn+1的超邊優(yōu)美雙射.

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

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

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

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

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

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

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

情況1n為偶數(shù).令輪輻標號為

路標號為

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

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

下面討論第1個扇圖其余各點導出的f+-值:

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

情況2n為奇數(shù).令輪輻標號為

路標號為

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

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

第1個扇圖其余各點導出的f+-值:

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

綜上,當n是正整數(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.

(責任編輯 向陽潔)

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

河北省教育廳科學研究項目(Z2013057)

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

O157

A

10.3969/j.issn.1007-2985.2014.02.003