探索圈龍圖的奇優(yōu)美性

孫慧，姚兵，2

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070;2. 蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

探索圈龍圖的奇優(yōu)美性

孫慧1，姚兵1，2

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070;2. 蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

圖的標(biāo)號(hào)是圖論的一個(gè)重要分支。定義了 2 種新圖——圈龍圖和多毛圈龍圖，并證明它們都具有奇優(yōu)美標(biāo)號(hào)。多毛圈龍圖是通過對(duì)圈龍圖加葉子得來的，證明他們繼承了圈龍圖的奇優(yōu)美性，證明方法能夠算法化，為圈龍圖和多毛圈龍圖應(yīng)用于網(wǎng)絡(luò)提供了可行的理論保證。

圈龍圖；多毛圈龍圖；集有序奇優(yōu)美標(biāo)號(hào)；奇優(yōu)美標(biāo)號(hào)；葉子；奇優(yōu)美圖

圖論作為數(shù)學(xué)的一大分支，起源于 1736 年的一個(gè)游戲——哥尼斯堡七橋問題。在隨后的 300 年間，圖論的研究迅速發(fā)展壯大，圖論的多個(gè)分支隨之誕生。圖的標(biāo)號(hào)作為圖論的一個(gè)重要分支起源于在 1967 年 Rosa 的一篇論文，他提出了著名而困難的優(yōu)美樹猜想，并在短短的50年間，特別是上世紀(jì)六十至八十年代，隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展和計(jì)算機(jī)的廣泛應(yīng)用，它的研究發(fā)展尤為迅速。如今，圖的標(biāo)號(hào)在現(xiàn)代科學(xué)技術(shù)中的諸多領(lǐng)域(計(jì)算機(jī)科學(xué)、信息科學(xué)、密碼學(xué)、數(shù)學(xué)證明等等)都得到廣泛地應(yīng)用。在進(jìn)攻 Rosa 的優(yōu)美樹猜想過程中，許多新的圖標(biāo)號(hào)不斷被發(fā)現(xiàn)，使得圖標(biāo)號(hào)成為圖論的一個(gè)龐大的分支[1- 8]。奇優(yōu)美標(biāo)號(hào)是圖標(biāo)號(hào)的重要種類[9]，文獻(xiàn)[10-15] 給出關(guān)于圖的奇優(yōu)美性的一些結(jié)果。本文受文獻(xiàn)[8,14]以及環(huán)形計(jì)算機(jī)網(wǎng)絡(luò)的啟發(fā)，發(fā)現(xiàn)兩類具有奇優(yōu)美標(biāo)號(hào)的新圖類——圈龍圖和多毛圈龍圖。

文中所考慮的圖均為有限、無向、簡(jiǎn)單圖。文中沒有定義的術(shù)語和符號(hào)參見文獻(xiàn)[15]。為方便起見，用記號(hào) [m,n] 表示集合{m,m+1,m+2,…,n}，其中m和n均為非負(fù)整數(shù)，且滿足 0≤m

一個(gè)(p,q)-圖G是指 |V(G)|=p和|E(G)|=q。圖G的一個(gè)從頂點(diǎn)集V(G) (或邊集E(G)，或全集V(G)∪E(G)) 到一個(gè)非負(fù)正數(shù)集的單射f是指任何 2 個(gè)不同頂點(diǎn)u,v(或 2 條邊或 2 個(gè)元素) 的像不同，即f(u) ≠f(v)，稱f為G的一個(gè)標(biāo)號(hào)(labeling)。以下頂點(diǎn)標(biāo)號(hào)集合{f(u)|u∈V(G)} 簡(jiǎn)記為f(V(G))，邊標(biāo)號(hào)集合 {f(uv)|uv∈E(G)} 簡(jiǎn)記為f(E(G))。

定義 1[14-15]對(duì)于給定的(p,q)-圖G，如果存在一個(gè)單射f:V(G) → [0,q]，使得邊標(biāo)號(hào)集合{f(uv)=|f(u)-f(v)‖uv∈E(G)}=[1,q]，則稱f是G的一個(gè)優(yōu)美標(biāo)號(hào)(graceful labeling)，也稱G為優(yōu)美圖(graceful graph)。此外，若圖G是具有頂點(diǎn)二部劃分 (X,Y) 的二部圖，且f滿足max{f(x)|x∈X}

定義 2 對(duì)于給定的(p,q)-圖G，如果存在一個(gè)單射f:V(G) → [0, 2q-1]，使得

f(E(G))={f(uv)=|f(u)-f(v)‖uv∈E(G)}=[1, 2q-1]o

則稱G為奇優(yōu)美圖(odd-graceful graph)，f是G的一個(gè)奇優(yōu)美標(biāo)號(hào)(odd-graceful labeling)。若圖G是具有頂點(diǎn)二部劃分(X,Y) 的二部圖，且f滿足f(X)

1 主要結(jié)論

證明 設(shè)f是G的奇優(yōu)美標(biāo)號(hào)?，F(xiàn)定義X={v|f(v) 是偶數(shù)}，Y={v|f(v) 是奇數(shù)}。顯然，V(G)=X∪Y以及X∩Y=?。由于G的每一條邊uv的標(biāo)號(hào)為奇數(shù)，所以X和Y都是獨(dú)立集。

其中F(n+1)=0。定義圈龍圖G的一個(gè)標(biāo)號(hào)函數(shù)f如下：

f(w)=s-F(1)+2n-3；

f(u1,2k-1)=F(2)+2k+2n-4，k∈[1,α(1)]

當(dāng)i∈[2,n]時(shí)，

f(ui,2k)=s-F(i+1)-2k+2n-2i+1，

k∈[1,α(i)]

f(ui ,2k-1) =

(i) 任何 2 個(gè)頂點(diǎn)的標(biāo)號(hào)互不相同，且對(duì)任意頂點(diǎn)u∈V(G)，總有f(u)∈[0, 2q-1]。在圈龍圖G的頭中，k按取值范圍取不同值時(shí)，圈龍圖G上的頂點(diǎn)標(biāo)號(hào)分別為：

f(u1,2)=s-F(2)+2n-3,f(u1,4)=

s-F(2)+2n-5,…,

f(u1,α(1)+1)=s-F(2)+2n-α(1)-2,

f(u1,α(1)+3)=s-F(2)+2n-α(1)-6,

f(u1,α(1)+5)=s-F(2)+2n-α(1)-8,…,

f(u1,a1-2)=s-F(2)+2n-a1-3,

f(u1,a1)=F(1)+2n-3,f(w)=

s-F(1)+2n-3,

圖1 圈龍圖Fig.1 A scheme of a cyclic dragon-graph D〈Ci

不難發(fā)現(xiàn)，在一個(gè)圈龍圖G中，不同的頂點(diǎn)ui,j(j=2k或j=2k-1)的標(biāo)號(hào)f(ui,j)彼此互不相同，那么，除了在圈Ci和Ci+1的公共頂點(diǎn)以外，當(dāng)i從1取到n時(shí)，任何兩個(gè)不同的頂點(diǎn)的標(biāo)號(hào)皆不相同。需要注意的是，2個(gè)圈Ci和Ci+1的公共頂點(diǎn)的頂點(diǎn)標(biāo)號(hào)是

此外，

這就證明：當(dāng)u≠v(u,v∈V(G))時(shí)，總有f(u)≠f(v)和f(V(G))?[0,2q-1]。

以及

以及

在圈龍圖G的頭中，當(dāng)k的取值范圍取不同時(shí)，圈龍圖G上的邊標(biāo)號(hào)取值分別為：

當(dāng)i∈[2,n]時(shí)，可計(jì)算出圈龍圖G上的邊ui,juk,l的標(biāo)號(hào)如下：

在圈龍圖G中，每一個(gè)邊標(biāo)號(hào)的值也取決于i和k，在同一個(gè)圈Ci上，不同的邊ui,jvi,l，當(dāng)k按取值范圍取不同值時(shí)，顯然邊標(biāo)號(hào)f(ui,jvi,l)彼此互不相同。

此外，

另一方面，在圈龍圖G的頭中，有

因?yàn)?/p>

綜合知：f滿足奇優(yōu)美標(biāo)號(hào)的定義且有f(X)

圖2是定理1的一個(gè)示例。

定理2 若圈龍圖D〈Ci〉n1滿足ai≡0(mod

4)(i∈[2,n])，a1≡2(mod 4)，那么在其上通過任意加葉子，得到的多毛圈龍圖HD〈Ci〉n1是奇優(yōu)美圖。

證明 令

其中

以及頂點(diǎn)標(biāo)號(hào)為g(ui,j)=g(ui)+g(uiui,j)(j∈[1,li]，i∈[2,s])。

3) 令g(v1v1,1)=2[M(s)+N(t)]-1,g(v1,1)=g(v1)-g(v1v1,1)，定義多毛圈龍圖G*的邊標(biāo)號(hào)為g(v1v1,l)=g(v1v1,1)-2(l-1)=2(M(s)+N(t))-2l+1(l∈[1,k1])，頂點(diǎn)標(biāo)號(hào)為g(v1,l)=g(v1)-g(v1v1,l)(l∈[1,k1])。最后定義多毛圈龍圖G*的邊標(biāo)號(hào)

圖2 解釋定理 1 的一個(gè)例子
Fig.2 An example for illustrating Theorem 1

另外，還有

進(jìn)一步，有

因?yàn)?/p>

所以，

因此，當(dāng)u≠v(u,v∈V(G*))時(shí)，總有g(shù)(u)≠g(v)，以及

多毛圈龍圖G*的邊標(biāo)號(hào)由 2 部分組成：

和

也就是說，

滿足奇優(yōu)美標(biāo)號(hào)的定義，定理2得證。

解釋定理2的一個(gè)例子在圖3中給出。

圖3 解釋定理2的一個(gè)例子Fig.3 An example for illustrating Theorem 2

2 總結(jié)與問題

本文通過探索圈龍圖和多毛圈龍圖的奇優(yōu)美性，定義了兩種新圖——圈龍圖和多毛圈龍圖，豐富了圖論中奇優(yōu)美圖的種類。定理 1 證明了圈龍圖具有集有序奇優(yōu)美標(biāo)號(hào)，定理2證明了多毛圈龍圖具有奇優(yōu)美標(biāo)號(hào)。但是，進(jìn)一步研究發(fā)現(xiàn)多毛圈龍圖則只具有奇優(yōu)美標(biāo)號(hào)，不再具有集有序的性質(zhì)。需要注意的是，本文的圈龍圖的圈Ci和Ci+1的連接點(diǎn)不能夠任意，那么連接點(diǎn)任意的圈龍圖的圖是否也具有奇優(yōu)美標(biāo)號(hào)呢? 另外，多毛圈龍圖是通過對(duì)圈龍圖加葉子得來的，并且良好的繼承了圈龍圖具有奇優(yōu)美標(biāo)號(hào)的性質(zhì)，那么這種加葉子的方法是不是可應(yīng)用于所有的圖，并且新圖是否依然繼承了原圖的標(biāo)號(hào)性質(zhì)，本文的圈龍圖是否具有其他有意義的標(biāo)號(hào)，這些都是今后需要繼續(xù)研究的課題。

[1] 魏麗俠, 張昆龍. 幾類并圖的優(yōu)美標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 47(3):10-13.WEILX,ZHANGKL.Gracefullabelingofseveralclassesofgraphs[J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2008, 47(3): 10-13.

[2] 趙喜楊, 姚兵. 探討樹的(k,d)-邊魔幻全標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(6): 67-73.ZHAOXY,YAOB.Discussionon(k,d)-edgemagictotallabeling[J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2016, 55(6):67-73.

[3] 唐保祥, 任韓. 2類優(yōu)美圖的冠的優(yōu)美標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 54(5): 24-27.TANGBX,RENH.Gracefullabelingof2kindsofgracefulgraphs[J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2015, 54(5): 24-27.

[4]CHENGH,YAOB,CHENXE,etal.Ongracefulgeneralizedspidersandcaterpillars[J].ArsCombinatoria, 2008, 87: 181-191.

[5] 姚明, 姚兵, 趙振學(xué), 等. 關(guān)于太陽圖魔幻標(biāo)號(hào)的若干結(jié)果[J]. 甘肅科學(xué)學(xué)報(bào), 2015, 27(4): 1-5.YAOM,YAOB,ZHAOZX,etal.Someresultsonthemagiclabelingofthesolargraph[J].JournalofGansuScience, 2015, 27(4): 1-5.

[6] 劉信生, 劉元元, 姚兵, 等. 龍圖的優(yōu)美性[J]. 蘭州理工大學(xué)學(xué)報(bào), 2013, 39(3): 133-135.LIUXS,LIUYY,YAOB,etal.Thegracefulnessofdragongraph[J].JournalofLanzhouUniversityofTechnology, 2013, 39(3): 133-135.

[7] 王宏宇, 姚兵, 楊超. 一類特殊對(duì)稱圖的邊魔幻性[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 36(1): 28-33.WANGHY,YAOB,YANGC.Edgemagicofaclassofspecialsymmetricgraphs[J].JournalofSichuanNormalUniversity(NaturalScienceEdition), 2013, 36(1): 28-33.

[8]FUMY,LIUXD,WANGLG.Thegracefulpropertyofakindofstringgraphs[J].JournalofSouthwestUniversityforNationalities, 2005, 31 (6):843-851.

[9]GANAJOTHIRB.Topicsingraphtheory[D].Madurai:MaduraiKamarajUniversity, 1991.

[10] 姚兵, 張家娟, 郭璟霞. 復(fù)合毛毛蟲樹的優(yōu)美及奇優(yōu)美性[J]. 蘭州理工大學(xué)學(xué)報(bào), 2012, 38(4): 147-150.YAOB,ZHANGJJ,GUOJX.Thegracefulandoddgracefulnessofthecompoundcaterpillartree[J].JournalofLanzhouUniversityofTechnology, 2012, 38(4): 147-150.

[11] 謝建民, 姚兵, 張銳. 兩類圈相關(guān)圖的奇優(yōu)美標(biāo)號(hào)[J]. 甘肅科學(xué)學(xué)報(bào), 2013, 25(4):1-3.XIEJM,YAOB,ZHANGR.Oddgracefullabelingoftwoclasscirclecorrelationgraphs[J].JournalofGansuScience, 2013, 25(4): 1-3.

[12] 劉信生, 劉元元, 姚兵, 等. 具有奇優(yōu)美性的一類龍圖[J]. 西南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 36(4): 47-51.LIUXS,LIUYY,YAOB,etal.Aclassofgraphswithoddgracefulness[J].JournalofSouthwesternUniversity(NaturalScienceEdition), 2014, 36(4): 47-51.

[13] 嚴(yán)謙泰. 積圖Pn×Pm的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2010, 30(3): 341-348.YANQT.ProductPn×Pmoddgracefulandoddstronglyharmonious[J].SystemScienceandMathematics, 2010, 30(3): 341-348.

[14]ZHOUXQ,YAOB,CHENXE,etal.Aprooftotheodd-gracefulnessofalllobsters[J].ArsCombinatoria-WaterloothenWinnipeg-, 2012, 103:13-18.

[15]JOSEPHAGALLIAN.Adynamicsurveyofgraphlabelling[J].TheElectronicJournalofCombinatorics, 2013,14:DS6.

Exploring the odd gracefulness of cyclic-dragon graphs

SUN Hui1, YAO Bing1，2

(1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China;2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

The labeling of Graph is an important branch of the graph theory. Two kinds of new graphs, cyclic-dragon graphs and haired cyclic-dragon graphs, are defined. It is proved that they are odd-graceful. The haired cyclic-dragon graphs is made by adding leaves to cyclic-dragon graphs, so they inherit the odd-graceful property of cyclic-dragon graphs, whose method can algorithm that may be a theoretical guarantee for applying cyclic-dragon graphs and haired cyclic-dragon graphs to network.

cyclic-dragon graphs; haired cyclic-dragon graphs; set-ordered odd-graceful labeling; odd-graceful labeling; leaf; odd-graceful graph

10.13471/j.cnki.acta.snus.2017.04.002

2016-12-16 基金項(xiàng)目：國(guó)家自然科學(xué)基金(61163054, 61363060, 61662066)

孫慧(1992年生)，女；研究方向：圖著色與標(biāo)號(hào)；E-mail：18919104606@163.com

姚兵(1956年生)，男；研究方向：圖著色與標(biāo)號(hào)、復(fù)雜網(wǎng)絡(luò)及優(yōu)化；E-mail：yybb918@163.com

O157.5

A

0529-6579(2017)04-0009-07