S(3，n)的k-边优美的图标号

刘晓珊， 王 琦

(1.河北地质大学 数理学院， 石家庄 050031； 2.河北经贸大学 研究生学院， 石家庄 050061)

S(3，n)的k-边优美的图标号

刘晓珊1*， 王 琦2

(1.河北地质大学 数理学院， 石家庄 050031； 2.河北经贸大学 研究生学院， 石家庄 050061)

设k为非负整数，G是一个p点q边图，如果将G的边用k，k+1，k+2，…，k+q-1进行标号，而顶点标号模p运算后各不相同，则称G是k-边优美的.对于所有满足G为k-边优美图的非负整数k所构成的集合称为图G的边优美指标集.该文给出了图G=(V，E)为k-边优美的定义，根据轮图的特殊性质，讨论了S(3，n)为k-边优美图的必要条件.根据所得的必要条件，利用递归的方法构造S(3，n)的k-边优美图标号并给出详细证明，从而完全解决了当n为偶数时S(3，n)的边优美指标集问题.

边优美图；k-边优美； 边优美指标集；S(3，n)图

一个图若含有p个顶点q条边，则称该图是(p，q)图.对于一个非负整数k，如果存在一个双射f:E→{k，k+1，k+2，…，k+q-1}，使得它的导出映射f+:V→Zp，uf(u，v)modp也是一个双射，那么就称(p，q)图G=(V，E)是k-边优美的.图S(3，n)是有3n+1个顶点的轮图，其中S(3，n)有3个圈，每个圈上有n个顶点，n≥3.其全部顶点为，并且O与相邻与相邻与相邻与相邻(1≤i≤n，1≤j≤2).对于一个给定的简单图G，称EGI(G)={k:G是k-边优美的}为图G的边优美指标集.下面通过具体构造，给出了当n为偶数时，图S(3，n)的k-边优美标号，从而确定其边优美指标集.

引理1对于一个非负整数k，若(p，q)图G是k-边优美的，则

引理2G是一个(p，q)图，s和m均为整数.如果G是s-边优美的，那么G也是(mp+s)-边优美的，即{k≥s:k≡smodp}⊆EGI(G)[1].

应用引理1的结论，可得到下面的引理，即图S(3，n)为k-边优美的必要条件.

1主要方法

为了找到一个映射F:E(S(3，n))→K，K={k，k+1，…，k+6n-1}，方法步骤如下：

2具体构造

构造2满足S(3，n)(n=2mod 4)是k￣-边优美的映射f构造如下：

3结论

证明由上述的直接构造可得到该定理的结论.

[1] 刘晓姗， 王 琦， 彭建萍.Cm×Cn的k-边美的图标号[J].江汉大学学报(自然科学版)， 2006， 34(3)：16-18.

[2] LEE S M， MURTY G. On edge-graceful labelings of complete graphs-solutions of Lo’s conjecture[J]. Congressum Numerantum， 1998， 62:225-233.

[3] GALLIAN J A. A Dynamic Survey of Graph Labeling [M]. The Electronic J of Combin， 2001， DS6: 1-79．

[4] LEE S M， SEAH E， LO S P. On edge-graceful 2-regular graphs [J]. The Journal of Combinatoric Mathematics and Combinatoric Computing， 1992， 12:109-117．

[5] CABANNIS S， MITCHEM J， LOW R. On edge-graceful regular graphs and trees[J]. Ars Combin， 1992， 34:129-142．

On thek-edge-graceful indices ofS(3，n)

LIU Xiaoshan1， WANG Qi2

(1.Institute of Mathematical and Physical Sciences， Hebei GEO University， Shijiazhuang 050031； 2.Graduate School， Hebei University of Economics & Business， Shijiazhuang 050061)

Letkbeanonnegativeinteger，andGbeagraphwithpverticesandqedges.ThegraphGiscalledtobek-edge-gracefulifthereexistsabijectionf:E→{k，k+1，k+2，…，k+q-1}suchthattheinducedmappingf+:V→Zpisabijectiontoo.WedenoteGisk-edge-graceful.Inthispaper，thedefinationisgivenoutwhichG=(V，E)iscalledtobek-edge-gracefulgraph.Andbytheespecialpropertyofthegraph，thenecessaryconditionwhichthegraphS(3，n)isk-edge-gracefulisdiscussed.Amethodtoconstructk-edge-gracefulgraphS(3，n)isgivenoutbyrecursionandtheproblemofwhatsetsofnaturalnumbersaretheedge-gracefulindicesofgraphS(3，n)iscompletelyresolvedwhenniseven.

edge-graceful graph;k-edge-graceful;edge-gracefulindex;S(3，n)graph

2017-01-03.

国家自然科学基金项目(11401158);河北省高等学校科学技术研究项目(QN2015240).

10.19603/j.cnki.1000-1190.2017.04.002

1000-1190(2017)04-0426-03

O157

A

*E-mail:wq80617@163.com.