贾慧羡，左大伟

(1.石家庄邮电职业技术学院基础部,河北 石家庄 050021;2.石家庄铁道大学数理系,河北 石家庄 050043)

与扇图相关的2类图的超边优美标号*

贾慧羡1，左大伟2

(1.石家庄邮电职业技术学院基础部,河北 石家庄 050021;2.石家庄铁道大学数理系,河北 石家庄 050043)

利用递归方法构造了扇图和图K1×2Pn的超边优美标号,证明了这2类图是超边优美图.

超边优美；扇图Fn+1；图K1×2Pn；图分解；轮辐标号；路标号

1985年,S.P.Lo[1]首次提出边优美图的概念,并给出边优美图的必要条件.关于图的边优美性,S.M.Lee[2]提出一个猜想:所有奇数阶的树都是边优美的.有关图的边优美性的更多结论,可参见文献[3].

1994年,J.Mitchem等[4]在讨论图的标号问题时提出超边优美图的定义.文献[3]中证明了K(1,n)当且仅当n是偶数时是超边优美的,双星图DS(m,n)当且仅当m,n都是奇数时是超边优美的,同时他们还猜想:所有奇数阶的树都是超边优美的.文献[5]给出了一些三正则图是超边优美的.目前,超边优美标号的研究还处于起步阶段,研究成果非常有限.

笔者首先讨论了扇图Fn+1的超边优美性.文献[6]中证明了n为偶数时扇图Fn+1是超边优美图,而对n为奇数的情况一直未解决.当n(n≠3)为奇数时,笔者利用递归构造证明扇图Fn+1是超边优美图,当n为偶数时,用另一种方法给出证明.从而,扇图Fn+1的超边优美性得到彻底解决.进而,笔者讨论了图K1×2Pn的超边优美性,证明当n>1时它是超边优美图.

1 预备知识

定义1 令

称(p,q)-图G是超边优美图.若存在一个双射f:E→Q,使得它的导出映射f+:V→P,u也是一个双射,则f称为图G的超边优美标号,集合P和Q相应称为图G的顶点值集和边标号集.

定义2Pn=v1v2...vn是顶点个数为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是整数,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的超边优美标号的构造

扇图Fn+1包含(n+1)个顶点和(2n-1)条边.易见,顶点数的奇偶性由n的奇偶性确定,边数为奇数,故定义1中的

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

因为n的奇偶性不同，所以文中分2种情况讨论:

现在的任务是定义一个双射f:E(Fn+1)→Q,使得它的导出映射f+:V(Fn+1)→P,u也是一个双射.

定理1 当n是正偶数时,扇图Fn+1是超边优美图.

证明令轮辐标号为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不是超边优美图.

定理3 当n为正奇数且n≠3时,扇图Fn+1是超边优美图.

证明令轮辐标号为

路标号为

轮辐标号恰充满集合[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个连续的整数,模去(n+1)必为顶点值集P.故f+:V(Fn+1)→P是一个双射.因此,f确是Fn+1的超边优美双射.

定理4 对正整数n(n≠3),扇图Fn+1是超边优美图.

由定理1、定理2和定理3,定理4的结论成立.

3 图K1×2Pn的超边优美标号的构造

图K1×2Pn包含(2n+1)个顶点和(4n-2)条边.易见,顶点数目为奇数，边数为偶数.故定义1中的

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

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

定理5 当n是正整数时,图K1×2Pn是超边优美图.

情况1n为偶数.令轮辐标号为

路标号为

轮辐标号恰充满集合[1,n-1]2∪[-(n-2),-2]∪{n},路标号恰充满集合[-(2n-1),-(n+1)]2∪[n+2,2n-2]2.可见,轮辐标号和路标号的绝对值恰充满集合[1,2n-1].又因为第2个扇图的边标号与第1个扇图上的边标号相反,所以按照上面规则和定义所得到的边标号恰充满集合Q,故f:E(K1×2Pn)→Q是一个双射.下面只需证明导出的各点的f+-值是V(K1×2Pn)→P的一个双射即可.

首先,根据2个扇图轮辐标号的规则,显然f+(v0)=0.

下面讨论第1个扇图其余各点导出的f+-值:

第1个扇图各点的f+-值恰充满集合{-n}∪[-(n-1),-1]∪[2,n-2]2,这些标号的绝对值集合恰为[1,n],按照上面规则可知,第2个扇图上的顶点(除中心v0外)标号等于第1个扇图定点标号的相反数,故所得到的顶点标号恰充满集合P,故f+:V(K1×2Pn)→P是一个双射.因此,f确是K1×2Pn的超边优美双射.

情况2n为奇数.令轮辐标号为

路标号为

轮辐标号恰充满集合[1,n-2]2∪[-(n-1),-2]∪{n},路标号恰充满集合[-(2n-2),-(n+1)]2∪[n+2,2n-1]2.可见,轮辐标号和路标号的绝对值恰充满集合[1,2n-1].又因为第2个扇图的边标号与第1个扇图上的边标号相反,所以按照上面规则和定义所得到的边标号恰充满集合Q,故f:E(K1×2Pn)→Q是一个双射.与前面类似,只需证明导出的各点的f+-值是V(K1×2Pn)→P的一个双射.

首先,根据2个扇图轮辐标号的规则,显然f+(v0)=0.

第1个扇图其余各点导出的f+-值:

第1个扇图各点的f+-值恰充满集合{-n}∪[-(n-2),-1]∪[2,n-1]2,这些标号的绝对值集合恰为[1,n],按照上面规则可知,第2个扇图上的顶点(除中心v0外)标号等于第1个扇图定点标号的相反数,所以所得到的顶点标号恰充满集合P,故f+:V(K1×2Pn)→P是一个双射.因此,f确是K1×2Pn的超边优美双射.

综上,当n是正整数时,K1×2Pn是超边优美图.

[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-),女,河北衡水人,石家庄邮电职业技术学院基础部讲师,硕士研究生,主要从事组合数学研究.

O157

A

10.3969/j.issn.1007-2985.2014.02.003