劉曉珊， 王 琦

(1.河北地質大學 數(shù)理學院， 石家莊 050031； 2.河北經貿大學 研究生學院， 石家莊 050061)

S(3，n)的k-邊優(yōu)美的圖標號

劉曉珊1*， 王 琦2

(1.河北地質大學 數(shù)理學院， 石家莊 050031； 2.河北經貿大學 研究生學院， 石家莊 050061)

設k為非負整數(shù)，G是一個p點q邊圖，如果將G的邊用k，k+1，k+2，…，k+q-1進行標號，而頂點標號模p運算后各不相同，則稱G是k-邊優(yōu)美的.對于所有滿足G為k-邊優(yōu)美圖的非負整數(shù)k所構成的集合稱為圖G的邊優(yōu)美指標集.該文給出了圖G=(V，E)為k-邊優(yōu)美的定義，根據(jù)輪圖的特殊性質，討論了S(3，n)為k-邊優(yōu)美圖的必要條件.根據(jù)所得的必要條件，利用遞歸的方法構造S(3，n)的k-邊優(yōu)美圖標號并給出詳細證明，從而完全解決了當n為偶數(shù)時S(3，n)的邊優(yōu)美指標集問題.

邊優(yōu)美圖；k-邊優(yōu)美； 邊優(yōu)美指標集；S(3，n)圖

一個圖若含有p個頂點q條邊，則稱該圖是(p，q)圖.對于一個非負整數(shù)k，如果存在一個雙射f:E→{k，k+1，k+2，…，k+q-1}，使得它的導出映射f+:V→Zp，uf(u，v)modp也是一個雙射，那么就稱(p，q)圖G=(V，E)是k-邊優(yōu)美的.圖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-邊優(yōu)美的}為圖G的邊優(yōu)美指標集.下面通過具體構造，給出了當n為偶數(shù)時，圖S(3，n)的k-邊優(yōu)美標號，從而確定其邊優(yōu)美指標集.

引理1對于一個非負整數(shù)k，若(p，q)圖G是k-邊優(yōu)美的，則

引理2G是一個(p，q)圖，s和m均為整數(shù).如果G是s-邊優(yōu)美的，那么G也是(mp+s)-邊優(yōu)美的，即{k≥s:k≡smodp}?EGI(G)[1].

應用引理1的結論，可得到下面的引理，即圖S(3，n)為k-邊優(yōu)美的必要條件.

1主要方法

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

2具體構造

構造2滿足S(3，n)(n=2mod 4)是k￣-邊優(yōu)美的映射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);河北省高等學?？茖W技術研究項目(QN2015240).

10.19603/j.cnki.1000-1190.2017.04.002

1000-1190(2017)04-0426-03

O157

A

*E-mail:wq80617@163.com.