K1×mCn的k-邊優(yōu)美指標(biāo)集

賈慧羨,左大偉

(1.石家莊郵電職業(yè)技術(shù)學(xué)院，河北 石家莊 050021；2.石家莊鐵道大學(xué)，河北 石家莊 050043)

K1×mCn的k-邊優(yōu)美指標(biāo)集

賈慧羨1,左大偉2

(1.石家莊郵電職業(yè)技術(shù)學(xué)院，河北 石家莊 050021；2.石家莊鐵道大學(xué)，河北 石家莊 050043)

設(shè)G=(V,E)是一個(gè)p點(diǎn)q邊圖.對(duì)于非負(fù)整數(shù)k, 若存在雙射f:E→{k,k+1,…,k+q-1}, 使得其導(dǎo)出映射

也是一個(gè)雙射,則稱此圖G是k-邊優(yōu)美的. 稱EGI(G)={k:G是k-邊優(yōu)美的}是G的邊優(yōu)美指標(biāo)集.在此徹底解決了圖K1×mCn(mn≡0 mod 2)的邊優(yōu)美指標(biāo)集.

k-邊優(yōu)美；邊優(yōu)美指標(biāo)集；K1×mCn圖

0 引 言

圖G=(V,E)是一個(gè)(p,q)圖.對(duì)于一個(gè)非負(fù)整數(shù)k,如果存在一個(gè)雙射f:E→{k,k+1,k+2,…,k+q-1},使得它的導(dǎo)出映射

也是一個(gè)雙射,則稱此圖G=(V,E)是k-邊優(yōu)美的.1-邊優(yōu)美圖是由Lo S P[1-2]引入的, 而k-邊優(yōu)美圖的概念是它的推廣.記EGI(G)={k:G是k-邊優(yōu)美的},稱EGI(G)是G的邊優(yōu)美指標(biāo)集.本文確定了圖K1×mCn(mn≡0 mod 2)的邊優(yōu)美指標(biāo)集.其它的圖標(biāo)號(hào)問(wèn)題可參見(jiàn)Gallian的綜述[3].

1 必要條件

引理1 設(shè)k是一個(gè)非負(fù)整數(shù),一個(gè)(p,q)-圖G是k-邊優(yōu)美的,則：

特別地，當(dāng)p≡2 mod 4時(shí),G不是k-邊優(yōu)美的.

引理2 設(shè)a,b是整數(shù),則同余方程ax≡bmodm有整數(shù)解僅當(dāng)gcd(a,m)|b. 特別的, 當(dāng)a,m為偶數(shù)且b為奇數(shù)時(shí),此同余方程無(wú)解.

此結(jié)論在數(shù)論中眾所周知.

證明圖K1×mCn含有(mn+1)個(gè)頂點(diǎn),2mn條邊. 由引理1,

即

即

2k≡3 mod (mn+1),

同余方程的解為:

引理4[5]設(shè)G是一個(gè)(p,q)-圖,s是一個(gè)整數(shù)且0≤s≤p-1,若G是s-邊優(yōu)美的, 則G是(mp+s)-邊優(yōu)美的.其中,m是任意正整數(shù).即EGI(G)?{k≥s:k≡s(modp)}.

2 構(gòu)造k-邊優(yōu)美K1×mCn的方法

為了找到一個(gè)映射F:E(K1×mCn)→K={k,k+1,k+2,…,k+2mn-1} (mn是偶數(shù)), 滿足圖K1×mCn是k-邊優(yōu)美的,采用如下的方法步驟.

設(shè)a,m為整數(shù)且m>0.方便起見(jiàn),采用如下記號(hào):

3 主要構(gòu)造

構(gòu)造1 當(dāng)m≡0 (mod 2)時(shí):

表1 當(dāng)m≡0(mod 2) 時(shí)各邊的f-值Tab. 1 The f-value of each edge when m≡0(mod 2)

因此得到表2.

表2 當(dāng)m≡0(mod 2) 時(shí)各頂點(diǎn)的f+-值Tab. 2 The f+-value of each vertex when m≡0(mod 2)

續(xù)表1

構(gòu)造2 當(dāng)m≡1 (mod 2),n≡0 (mod 2)時(shí):

表3 當(dāng)m≡1(mod 2), n≡0(mod 2)時(shí)各邊的f-值Tab. 3 The f-value of each edge when m≡1 (mod 2), n≡0 (mod 2)

因此得到表4.

表4 當(dāng)m≡1(mod 2), n≡0 (mod 2)時(shí)各頂點(diǎn)的f+-值Tab. 4 The f+-value of each vetex when m≡1(mod 2), n≡0(mod 2)

4 結(jié) 論

證明由上述構(gòu)造可直接得到此定理.

[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)

k-edge-graceful; edge-graceful indices; graphK1×mCn

2012-04-04

賈慧羨(1979—),女,講師,碩士研究生，主要從事組合數(shù)學(xué)研究.E-mail:jiaxian676710@163.com

11.3969/j.issn.1674-232X.2012.05.013

O157MSC2010: 05C78

A

1674-232X(2012)05-0447-06