單圈圖的邊優(yōu)美性

陳淑貞, 薛茗曦

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

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

1 相關(guān)定義

以下所定義和研究的圖均為簡單圖.

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

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

定義4 在回路Cm的一個頂點處粘接兩條路所組成的單圈圖稱為風箏圖,記為Ω(m,2).

2 主要結(jié)果

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

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

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

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

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

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

由f導出的點標號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).

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

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

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

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

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

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

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

證明設(shè)Ω2(m,2)的頂點數(shù)為2n+1(n>3)個，且有|V(Ω2)|= |E(Ω2)|= 2n+1.如圖3所示，定靶圖Ω2(m,2)的頂點依次記為a1,a2,…，ai,…，a2n+1，其中兩條路的長分別為i+1和i,回路中的點數(shù)m為2n-2i.定義其邊標號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.

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

由f導出的點標號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個數(shù)恰好取遍集合{1,3,5,…,2i+1,2i+3, …,4i+5,4i+7,4i+9, …,4n-3,4n-1,4n+1}中的2n+1個數(shù)，顯然取模|V(Ω2)|后點標號一一對應(yīng)于{0,1,2,…,2n}. 所以f的導出映射f*是V(Ω2)到{0,1,2,…,2n}雙射,于是定靶圖Ω2(m,2)為邊優(yōu)美圖.圖4給出了定靶圖Ω2(m,2)的邊優(yōu)美標號.

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

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

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

證明Ω(m,2)的頂點數(shù)為2n+1(n>1)個，則有|V(Ω)|= |E(Ω)|= 2n+1.如圖5所示，風箏圖的頂點依次記為a1,a2,…，ai,…，a2n+1.定義其邊標號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.

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

由f導出的點標號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).

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

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

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

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

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

圖6 奇階圖Ω(m,2)的邊優(yōu)美標號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]康慶德. 圖標號問題[J]. 河北師范學院學報，1991(1):102-115.

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

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

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