陳淑貞, 薛茗曦

(海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，海南 ?？?571158)

圖標(biāo)號(hào)問(wèn)題由Ringel G和Rosa A在上世紀(jì)60年代中期提出并引起國(guó)內(nèi)外許多學(xué)者的關(guān)注[1,2]，已成為圖論中一個(gè)重要而活躍的研究分支.從圖的優(yōu)美標(biāo)號(hào)被提出到現(xiàn)在已有三十來(lái)種圖標(biāo)號(hào)被定義[3].單圈圖(只含一個(gè)圈的圖)是一類(lèi)重要的圖形. 1984年，Truszczynski M關(guān)于單圈圖的猜想: 除Cn(n≡1,2(mod 4))外，所有的單圈圖都是優(yōu)美的[4]. 從那時(shí)起，關(guān)于單圈圖的研究一直未間斷過(guò)，至今已有許多研究成果[3-8].1985年，Lo S引入邊優(yōu)美圖的概念[9]，并給出邊優(yōu)美圖的必要條件. 對(duì)圖的邊優(yōu)美性的研究雖然已取得一些研究成果,但仍有許多問(wèn)題尚待解決. 關(guān)于單圈圖的邊優(yōu)美性有一個(gè)重要猜想[5]：奇階單圈圖是邊優(yōu)美的.本文研究了奇階單圈圖的邊優(yōu)美性問(wèn)題，給出三類(lèi)奇階單圈圖的邊優(yōu)美標(biāo)號(hào).

1 相關(guān)定義

以下所定義和研究的圖均為簡(jiǎn)單圖.

定義2 在回路Cm相鄰的兩個(gè)頂點(diǎn)處分別粘接一條路所組成的單圈圖稱(chēng)為靶圖,記為Ω1(m,2).

定義3 在回路Cm相距為2的兩個(gè)頂點(diǎn)處分別粘接一條路所組成的單圈圖稱(chēng)為定靶圖,記為Ω2(m,2).

定義4 在回路Cm的一個(gè)頂點(diǎn)處粘接兩條路所組成的單圈圖稱(chēng)為風(fēng)箏圖,記為Ω(m,2).

2 主要結(jié)果

定理1 奇階靶圖Ω1(m,2)是邊優(yōu)美圖.

證明設(shè)Ω1(m,2)的頂點(diǎn)數(shù)為2n+1(n>1)個(gè)，其中圈中有m個(gè)點(diǎn)，且有

|V(Ω1)|= |E(Ω1)|= 2n+1,

如圖1所示，靶圖Ω1(m,2)的頂點(diǎn)依次記為a1,a2,…，ai,…，a2n+1.定義其邊標(biāo)號(hào)f如下：

f(akak+1)=k(k=1,2,…，2n),f(ai+1ai+m)=2n+1.

顯然，邊標(biāo)號(hào)f是E(Ω1)到{1,2,3,…,2n+1}的雙射.

由f導(dǎo)出的點(diǎn)標(biāo)號(hào)f*為：

f*(ak)=k-1+k=2k-1(k=1,2,…,n)，f*(an+k)=[2n+2k-1](mod|V(Ω1)|)=2k-2(k=1,2,…，n+1).

特別地，頂點(diǎn)ai+1和ai+m有三條相關(guān)聯(lián)的邊，但多出的邊ai+1ai+m滿(mǎn)足

f(ai+1ai+m)=2n+1,

以上計(jì)算結(jié)果仍然成立.

顯然，f的導(dǎo)出映射f*是V(Ω1)到{0,1,2,…,2n}雙射,所以靶圖Ω1(m,2)是邊優(yōu)美圖.圖2給出了靶圖Ω1(m,2)的邊優(yōu)美標(biāo)號(hào).

圖1 奇階圖Ω1(m,2)Fig. 1 The odd degree graph Ω1(m,2)

圖2 奇階圖Ω1(m,2)的邊優(yōu)美標(biāo)號(hào)Fig.2 The edge-graceful labeling of odd degree graph Ω1(m,2)

定理2 當(dāng)回路上的點(diǎn)為偶數(shù)，且兩條路的長(zhǎng)度相差為1時(shí)，奇階定靶圖Ω2(m,2)是邊優(yōu)美圖.

證明設(shè)Ω2(m,2)的頂點(diǎn)數(shù)為2n+1(n>3)個(gè)，且有|V(Ω2)|= |E(Ω2)|= 2n+1.如圖3所示，定靶圖Ω2(m,2)的頂點(diǎn)依次記為a1,a2,…，ai,…，a2n+1，其中兩條路的長(zhǎng)分別為i+1和i,回路中的點(diǎn)數(shù)m為2n-2i.定義其邊標(biāo)號(hào)f如下：

f(akak+1)=k(k=1,2,…,2i+3,2i+5,…,2n)，f(ai+2a2i+5)=2i+4，f(a2n+1ai+4)=2n+1.

顯然，邊標(biāo)號(hào)f是E(Ω2)到{1,2,3,…,2n+1}的雙射.

由f導(dǎo)出的點(diǎn)標(biāo)號(hào)f*在取模|V(Ω2)|前為：

f*(ak)=2k-1(k=1,2,…，i+1),f*(ai+2)=4i+7,f*(a2i+4)=2i+3,
f*(ai+k)=2i+2k-1(k=3,4,5,…,i+3,i+5,…,2n+1-i).

這2n+1個(gè)數(shù)恰好取遍集合{1,3,5,…,2i+1,2i+3, …,4i+5,4i+7,4i+9, …,4n-3,4n-1,4n+1}中的2n+1個(gè)數(shù)，顯然取模|V(Ω2)|后點(diǎn)標(biāo)號(hào)一一對(duì)應(yīng)于{0,1,2,…,2n}. 所以f的導(dǎo)出映射f*是V(Ω2)到{0,1,2,…,2n}雙射,于是定靶圖Ω2(m,2)為邊優(yōu)美圖.圖4給出了定靶圖Ω2(m,2)的邊優(yōu)美標(biāo)號(hào).

圖3 奇階圖Ω2(m,2)Fig.3 The odd degree graph Ω2(m,2)

圖4 奇階圖Ω2(m,2)的邊優(yōu)美標(biāo)號(hào)Fig.4 The edge-graceful labeling of odd degree graph Ω2(m,2)

定理3 一條路為n的2n+1階風(fēng)箏圖Ω(m,2)是邊優(yōu)美圖.

證明Ω(m,2)的頂點(diǎn)數(shù)為2n+1(n>1)個(gè)，則有|V(Ω)|= |E(Ω)|= 2n+1.如圖5所示，風(fēng)箏圖的頂點(diǎn)依次記為a1,a2,…，ai,…，a2n+1.定義其邊標(biāo)號(hào)f如下：

f(akak+1)=k(k=1,2,…，n-1),f(akak+1)=k+1(k=n+1,n+2,…，2n),
f(anan+m)=n,
f(an+1an+m)=n+1.

顯然,邊標(biāo)號(hào)f是E(Ω)到{1,2,3,…,2n+1}的雙射.

由f導(dǎo)出的點(diǎn)標(biāo)號(hào)f*為：

f*(ak)=2k-1(k=1,2,…n),
f*(a2n+1)=2n+1(mod|V(Ω)|)=0,
f*(an+k)=[2n+2k+1](mod|V(Ω)|)=2k(k=1,2,…,n).

特別地，頂點(diǎn)an+m有四條相關(guān)聯(lián)的邊，但多出的邊an+1an+m和anan+m滿(mǎn)足

f(an+1an+m)+f(anan+m)=2n+1,

以上計(jì)算結(jié)果仍然成立.

顯然，f的導(dǎo)出映射f*是V(Ω)到{0,1,2,…,2n}雙射.于是風(fēng)箏圖Ω(m,2)是邊優(yōu)美圖. 圖6給出了風(fēng)箏圖Ω(m,2)的邊優(yōu)美標(biāo)號(hào).

圖5 奇階圖 Ω(m,2)Fig.5 The odd degree graph Ω(m,2)

圖6 奇階圖Ω(m,2)的邊優(yōu)美標(biāo)號(hào)Fig.6 The edge-graceful labeling of odd degree graph Ω(m,2)

[1] Ringel G. Problem 25 in theory of graphs and its application[C]// Proceedings of the Symposium Smolenice，1963. Prague Publ: House of Czcchoslovak Academy of Science, 1964.

[2] Rosa A. On certain valuations of the vertices of a graph[C]// Theory of Graphs International Symposium, Rome, 1966. Newyork and Dunod Paris: Gordon and Breach, 1967: 349-355.

[3]Gallian J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2016, Dynamic Surveys 6: 1-408.

[4]Truszczynski M. Graceful unicycle graphs[J]. Demonstration Math, 1984, 17: 377-387.

[5]康慶德. 圖標(biāo)號(hào)問(wèn)題[J]. 河北師范學(xué)院學(xué)報(bào)，1991(1):102-115.

[7]陳淑貞, 王麗娜. Ω(2, k, n)型圖的優(yōu)美性[J]. 海南師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 21(3)： 249-253.

[8]鄭學(xué)謙. 圖Cn×K2的邊優(yōu)美標(biāo)號(hào)的研究[J]. 太原師范學(xué)院學(xué)報(bào)，2012,11(4):12-13.

[9]Lo S. On edge-graceful labelings of graphs[J]. Congressus Numerantium, 1985(50): 231-241.