K1×mCn的k-边优美指标集

2012-11-14贾慧羡左大伟

杭州师范大学学报(自然科学版) 2012年5期

关键词：大伟偶数铁道

贾慧羡,左大伟

(1.石家庄邮电职业技术学院，河北石家庄 050021；2.石家庄铁道大学，河北石家庄 050043)

K1×mCn的k-边优美指标集

贾慧羡1,左大伟2

(1.石家庄邮电职业技术学院，河北石家庄 050021；2.石家庄铁道大学，河北石家庄 050043)

设G=(V,E)是一个p点q边图.对于非负整数k, 若存在双射f:E→{k,k+1,…,k+q-1}, 使得其导出映射

也是一个双射,则称此图G是k-边优美的. 称EGI(G)={k:G是k-边优美的}是G的边优美指标集.在此彻底解决了图K1×mCn(mn≡0 mod 2)的边优美指标集.

k-边优美；边优美指标集；K1×mCn图

0 引言

图G=(V,E)是一个(p,q)图.对于一个非负整数k,如果存在一个双射f:E→{k,k+1,k+2,…,k+q-1},使得它的导出映射

也是一个双射,则称此图G=(V,E)是k-边优美的.1-边优美图是由Lo S P[1-2]引入的, 而k-边优美图的概念是它的推广.记EGI(G)={k:G是k-边优美的},称EGI(G)是G的边优美指标集.本文确定了图K1×mCn(mn≡0 mod 2)的边优美指标集.其它的图标号问题可参见Gallian的综述[3].

1 必要条件

引理1 设k是一个非负整数,一个(p,q)-图G是k-边优美的,则：

特别地，当p≡2 mod 4时,G不是k-边优美的.

引理2 设a,b是整数,则同余方程ax≡bmodm有整数解仅当gcd(a,m)|b. 特别的, 当a,m为偶数且b为奇数时,此同余方程无解.

此结论在数论中众所周知.

证明图K1×mCn含有(mn+1)个顶点,2mn条边. 由引理1,

即

2k≡3 mod (mn+1),

同余方程的解为:

引理4[5]设G是一个(p,q)-图,s是一个整数且0≤s≤p-1,若G是s-边优美的, 则G是(mp+s)-边优美的.其中,m是任意正整数.即EGI(G)⊆{k≥s:k≡s(modp)}.

2 构造k-边优美K1×mCn的方法

为了找到一个映射F:E(K1×mCn)→K={k,k+1,k+2,…,k+2mn-1} (mn是偶数), 满足图K1×mCn是k-边优美的,采用如下的方法步骤.

设a,m为整数且m>0.方便起见,采用如下记号:

3 主要构造

构造1 当m≡0 (mod 2)时:

表1 当m≡0(mod 2) 时各边的f-值Tab. 1 The f-value of each edge when m≡0(mod 2)

因此得到表2.

表2 当m≡0(mod 2) 时各顶点的f+-值Tab. 2 The f+-value of each vertex when m≡0(mod 2)

续表1

构造2 当m≡1 (mod 2),n≡0 (mod 2)时:

表3 当m≡1(mod 2), n≡0(mod 2)时各边的f-值Tab. 3 The f-value of each edge when m≡1 (mod 2), n≡0 (mod 2)

因此得到表4.

表4 当m≡1(mod 2), n≡0 (mod 2)时各顶点的f+-值Tab. 4 The f+-value of each vetex when m≡1(mod 2), n≡0(mod 2)

4 结论

证明由上述构造可直接得到此定理.

[1] Lee Sin-Min, Seah Eric. On the edge-graceful (n,kn)-multigraphs conjecture[J]. Journal of Combinatorial Mathematics and Combinatorial Computing,1991,9:141-147.

[2] Lee Sin-Min, Seah E, Lo S P. On edge-graceful 2-regular graphs[J]. Journal of Combinatoric Mathematics and Combinatoric Computing,1992,12:109-117.

[3] Gallian J A. A dynamic survey of graph labeling[J]. The Electronic J of Combinatorics,2011,18(DS6)：1-79.

[4] Lee Sin-Min, Murty G. On edge-graceful labelings of complete graphs-solutions of Lo’s conjecture[J]. Congressum Numerantum,1988,62:225-233.

[5] Lee Sin-Min, Wang Ling, Kang Qingde. On the edge-graceful indices of the wheel graphs[J]. submitted to Discrete Mathematics.

TheEdge-GracefulIndicesoftheGraphK1×mCn

JIA Hui-xian1, ZUO Da-wei2

(1. Shijiazhuang Post and Telecommunication Technical College, Shijiazhuang 050021, China;2. Shijiazhuang Tiedao University, Shijiazhuang 050043, China)