孫 慧， 姚 兵*,2

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

關(guān)于圈龍圖的奇優(yōu)雅性

孫 慧1， 姚 兵*1,2

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

圖的標(biāo)號(hào)主要有 (奇) 優(yōu)美標(biāo)號(hào)、和諧標(biāo)號(hào)、幸福標(biāo)號(hào)、魔幻類(lèi)標(biāo)號(hào)等．圈龍圖和多毛圈龍圖可以作為計(jì)算機(jī)網(wǎng)絡(luò)的模型．證明了圈龍圖和多毛圈龍圖都具有奇優(yōu)雅標(biāo)號(hào)，證明方法能夠算法化，為網(wǎng)絡(luò)模型的密碼和可區(qū)別性研究提供了理論依據(jù)和可行的工具．

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

0 引 言

圖標(biāo)號(hào)研究起源于1967年Rosa的著名的優(yōu)美樹(shù)猜想[1]．根據(jù)不同的條件，產(chǎn)生了各種類(lèi)型的圖標(biāo)號(hào)，例如優(yōu)美標(biāo)號(hào)、奇優(yōu)美標(biāo)號(hào)、和諧標(biāo)號(hào)、幸福標(biāo)號(hào)、魔幻類(lèi)標(biāo)號(hào)等．圖的標(biāo)號(hào)在現(xiàn)代科學(xué)技術(shù)的諸多領(lǐng)域(計(jì)算機(jī)科學(xué)、信息科學(xué)、密碼學(xué)、數(shù)學(xué)證明等)都得到了廣泛應(yīng)用．因此，圖標(biāo)號(hào)成為圖論學(xué)科中發(fā)展迅速的分支之一[2-8]．文獻(xiàn)[8]收錄了1 400多篇關(guān)于圖標(biāo)號(hào)的文章．而周向前[9]在2012年提出奇優(yōu)雅標(biāo)號(hào)的概念，給出若干構(gòu)造奇優(yōu)雅標(biāo)號(hào)的方法，并給出一個(gè)猜想:所有的樹(shù)都是奇優(yōu)雅的．文獻(xiàn)[9-13]是一些關(guān)于奇優(yōu)雅標(biāo)號(hào)的研究結(jié)果．Wang等在文獻(xiàn)[14]中提出了“圖結(jié)構(gòu)+數(shù)論”的新型密碼設(shè)計(jì)思想，目的是設(shè)計(jì)使用者方便、破譯困難的圖結(jié)構(gòu)密碼．這種設(shè)計(jì)需要足夠多的圖結(jié)構(gòu)、圖標(biāo)號(hào)、靈活組合的策略．受文獻(xiàn)[7，10]和環(huán)形計(jì)算機(jī)網(wǎng)絡(luò)的啟發(fā)，以及為Wang等的設(shè)計(jì)提供新的具有奇優(yōu)雅性質(zhì)的圖結(jié)構(gòu)，本文討論與計(jì)算機(jī)網(wǎng)絡(luò)有關(guān)聯(lián)的圈龍圖和多毛圈龍圖網(wǎng)絡(luò)模型．圈龍圖是一種典型的環(huán)形計(jì)算機(jī)網(wǎng)絡(luò)，每個(gè)頂點(diǎn)可以看作一個(gè)服務(wù)器；而多毛圈龍圖是給圈龍圖的任意頂點(diǎn)添加任意葉子得到的，一個(gè)葉子的頂點(diǎn)代表一個(gè)連接某一服務(wù)器的用戶(hù)，多毛圈龍圖是給圈龍圖任意添加葉子的過(guò)程，它模擬了用戶(hù)登錄服務(wù)器的過(guò)程．文獻(xiàn)[7]研究的模型也是一種環(huán)形計(jì)算機(jī)網(wǎng)絡(luò)模型，但與本文研究的圈龍圖略有不同，且文獻(xiàn)[7]沒(méi)有多毛圈龍圖網(wǎng)絡(luò)模型．

1 定 義

文中所考慮的圖均為有限、無(wú)向、簡(jiǎn)單圖．文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)[15]．為方便起見(jiàn)，用記號(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)，稱(chēng)f為G的一個(gè)標(biāo)號(hào)(labelling)．以下頂點(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[8,16]對(duì)于給定的(p，q)-圖G，如果存在一個(gè)單射f：V(G)→[0，q]，使得邊標(biāo)號(hào)集合f(E(G))={f(uv)=f(u)-f(v)|uv∈E(G)}=[1，q]，則稱(chēng)f是G的一個(gè)優(yōu)美標(biāo)號(hào)(graceful labelling)，也稱(chēng)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，則稱(chēng)G為奇優(yōu)美圖(odd-graceful graph)，f是G的一個(gè)奇優(yōu)美標(biāo)號(hào)(odd-graceful labelling)．若圖G是具有頂點(diǎn)二部劃分(X，Y)的二部圖，且f滿足f(X)

定義3[10]對(duì)于給定的(p，q)-圖G，如果存在一個(gè)單射f：V(G)→[0，2q-1]，使得f(V(G))=p和f(E(G))={f(uv)=[f(u)+f(v)](mod 2q)|uv∈E(G)}=[1，2q-1]o，則稱(chēng)G為奇優(yōu)雅圖(odd-elegant graph)，f是G的一個(gè)奇優(yōu)雅標(biāo)號(hào)(odd-elegant labelling)．

圖1 圈龍圖

2 主要結(jié)論

證明設(shè)f是G的奇優(yōu)雅標(biāo)號(hào)．現(xiàn)定義X={v|f(v)是偶數(shù)，v∈f(v)}，Y={v|f(v)是奇數(shù)，v∈f(v)}．顯然，V(G)=X∪Y以及X∩Y=?．因?yàn)镚是奇優(yōu)雅的，所以X和Y都是獨(dú)立集．

□

f(w)=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)=F(i+1)+2k-2n+2i-1；k∈[1，α(i)]

另外，邊標(biāo)號(hào)集合f(E(G))={f(uv)=[f(u)+f(v)](mod 2q)|uv∈E(G)}．

(1)先證明f(V(G))?[0，2q-1]，以及對(duì)于任意的頂點(diǎn)u，v∈V(G)，有f(u)≠f(v)．

不難看出每個(gè)f(ui，2k-1)(i∈[1，n]，k∈[1，α(i)])是偶數(shù)，每個(gè)f(ui，2k)(i∈[1，n]，k∈[1，α(i)])和f(w)是奇數(shù)．令X={ui，2k-1|ui，2k-1∈V(G)，i∈[1，n]，k∈[1，α(i)]}，Y={ui，2k|ui，2k∈V(G)，i∈[1，n]，k∈[1，α(i)]}∪{w}．注意到，當(dāng)i∈[1，n]時(shí)，有f(ui，2k-1)f(w)，f(w)>f(u1，a1-2)，f(u1，2k)>f(u1，2(k-1))(k∈[2，α(1)-1])；當(dāng)i∈[2，n]時(shí)，有f(ui，2k)>f(ui，2(k-1))(k∈[2，α(i)])．此外，f(un，1)=0，f(u1，a1-1)=F(2)+2n+a1-4

因此，f(V(G))?[0，2q-1]，對(duì)于任意的頂點(diǎn)u，v，u≠v，有f(u)≠f(v)．

因此，f(E(G))=[1，2q-1]o，對(duì)于任意的邊uv，xy∈E(G)，有f(uv)≠f(xy)．

綜合知：f滿足奇優(yōu)雅標(biāo)號(hào)的定義，定理證明完畢．

□

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

圖2 解釋定理1的一個(gè)例子

(i)令g(ui)=f(ui)(i∈[1，s])，g(vj)=f(vj)(j∈[1，t])．

(ii)令g(u1u1，1)=2q′-1，g(u1，1)=g(u1u1，1)-g(u1)=2q′-1，其中g(shù)(u1)=0．定義多毛圈龍圖G*的邊標(biāo)號(hào)為g(u1u1，j)=2q′+1-2j(j∈[1，l1])，其頂點(diǎn)標(biāo)號(hào)為g(u1，j)=g(u1u1，j)-g(u1)=2q′+1-2j(j∈[1，l1])．

根據(jù)標(biāo)號(hào)g的定義，有g(shù)(uiui，j)=[g(ui，j)+g(ui)](mod 2q′)=g(ui，j)+g(ui)(j∈[1，li]，i∈[1，s])．g(vivi，j)=[g(vi，j)+g(vi)](mod 2q′)=g(vi，j)+g(vi)(j∈[1，ki]，i∈[1，t])．

下面證明g是多毛圈龍圖G*的奇優(yōu)雅標(biāo)號(hào)，敘述里省略“(mod 2q′)”．

(1)下證g：V(G*)→[0，2q′-1]．對(duì)于任意的頂點(diǎn)u，v∈V(G*)，有g(shù)(u)≠g(v)．

顯然，每個(gè)g(ui)(i∈[1，s])是偶數(shù)，每個(gè)g(vj)(j∈[1，t])是奇數(shù)；每個(gè)g(ui，j)(j∈[1，li]，i∈[1，s])是奇數(shù)，每個(gè)g(vl，r)(r∈[1，kl]，l∈[1，t])是偶數(shù)．注意到0≤g(ui)

根據(jù)標(biāo)號(hào)g的定義，有g(shù)(uiui，j)>g(uiui，j+1)≥2q+1(j∈[1，li-1]，i∈[1，s])；g(uiui，li)>g(ui+1ui+1，1)≥2q+1(i∈[1，s-1])；2q+1≤g(vivi，j)g(ui，j+1)>0(j∈[1，li-1]，i∈[1，s])，2q′-1≥g(ui，li)>g(ui+1，1)>0(i∈[1，s-1])；0

因?yàn)?/p>

g(usv1)=g(v1)+g(us)=2q-1，

g(v1v1，1)=g(v1)+g(v1，1)=2q+1

以及

因此g(us，ls)>g(v1)，g(v1，1)>g(us)．故當(dāng)u≠v(u，v∈V(G*))時(shí)，總有g(shù)(u)≠g(v)，g(V(G*))?[0，2|E(G*)|-1]．

(2)證明g(E(G*))=[1，2q′-1]o．多毛圈龍圖G*的邊標(biāo)號(hào)由兩部分組成：{g(uv)|uv∈E(G*)-E(G)}=[2q+1，2q′-1]o和{g(uv)|uv∈E(G)?E(G*)}=[1，2q-1]o，也就是說(shuō)，g(E(G*))=[1，2E(G*)-1]o，滿足奇優(yōu)雅標(biāo)號(hào)的定義，定理2得證．

□

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

圖3 解釋定理2的一個(gè)例子

3 結(jié) 語(yǔ)

本文探索了圈龍圖和多毛圈龍圖的奇優(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)呢?另外，多毛圈龍圖是通過(guò)對(duì)圈龍圖加葉子得來(lái)的，并且良好地繼承了圈龍圖具有奇優(yōu)雅標(biāo)號(hào)的性質(zhì)，那么這種加葉子的方法是不是可以應(yīng)用于所有的圖，并且新圖是否依然繼承了原圖的標(biāo)號(hào)性質(zhì)，這些都是今后需要繼續(xù)研究的課題．

[1] ROSA A. On certain valuation of the vertices of a graph [M] // ROSENSTIEHL P.TheoryofGraphs. New York: Gordon and Breach, 1967:349-355.

[2] CHENG Hui, YAO Bing, CHEN Xiang′en,etal. On graceful generalized spiders and caterpillars [J].ArsCombinatoria, 2008,87:181-191.

[3] KOTZIG A, ROSA A. Magic valuations of finite graphs [J].CanadianMathematicalBulletin, 1970,13:451-461.

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

YAO Ming, YAO Bing, ZHAO Zhenxue. Some results on the magic labelling of sun-graphs [J].JournalofGansuSciences, 2015,27(4):1-5. (in Chinese)

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

LIU Xinsheng, LIU Yuanyuan, YAO Bing,etal. Gracefulness of dragon graphs [J].JournalofLanzhouUniversityofTechnology, 2013,39(3):133-135. (in Chinese)

[6] 王宏宇,姚 兵,楊 超. 一類(lèi)特殊對(duì)稱(chēng)圖的邊魔幻性 [J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013,36(1):28-33.

WANG Hongyu, YAO Bing, YANG Chao. The edge-magic property of a special class of edge-symmetric graphs [J].JournalofSichuanNormalUniversity(NaturalScience), 2013,36(1):28-33. (in Chinese)

[7] FU Mingyan, LIU Xiaodong, WANG Ligong,etal. The graceful property of a kind of string graphs [J].JournalofSouthwestUniversityforNationalities(NaturalScienceEdition), 2005,31(6):843-851.

[8] GALLIAN J A. A dynamic survey of graph labeling [J].TheElectronicJournalofCombinatorics, 2013,14:DS6.

[9] 周向前. 關(guān)于圖的優(yōu)美、奇優(yōu)美、奇優(yōu)雅標(biāo)號(hào)的研究[D]. 蘭州:西北師范大學(xué), 2012.

ZHOU Xiangqian. The research on graceful, odd-graceful and odd-elegant labelings of graphs [D]. Lanzhou:Northwest Normal University, 2012. (in Chinese)

[10] ZHOU Xiangqian, YAO Bing, CHEN Xiang′en. Every lobster is odd-elegant [J].InformationProcessingLetters, 2013,113(1/2):30-33.

[11] YANG Sihua, YAO Bing, ZHANG Wanjia,etal. On odd-elegant properties of generalized sun-graphs [C] //2014IEEE7thJointInternationalInformationTechnologyandArtificialIntelligenceConference,ITAIC2014. Piscataway: IEEE, 2014:392-396.

[12] XIE Jianmin, YAO Bing, ZHAO Tinggang. An algorithm and its implementation for odd-elegant labeling of general sun graphSm,n[J].JournalofShandongUniversity(NaturalScience), 2016,51(4):79-85.

[13] XIE Jianmin, YAO Bing, HONG Wenmei. Odd-elegant labeling algorithm of generalized ring core networks [C] //20166thInternationalConferenceonMachinery,Materials,Environment,BiotechnologyandComputer(MMEBC2016). Amsterdam: Atlantis Press, 2016.

[14] WANG Hongyu, XU Jin, YAO Bing. Exploring new cryptographical construction of complex network data [C] //2016IEEEFirstInternationalConferenceonDataScienceinCyberspace(DSC). Piscataway: IEEE, 2016:155-160.

[15] BONDYJ A, MURTY U S R.GraphTheorywithApplications[M]. Amsterdam: North-Holland, 1976.

[16] ZHOU Xiangqian, YAO Bing, CHEN Xiang′en,etal. A proof to the odd-gracefulness of all lobsters [J].ArsCombinatoria, 2012,103:13-18.

Onodd-elegantqualityofcyclic-dragongraphs

SUN Hui1, YAO Bing*1,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 )

Graph labellings mainly include (odd-)graceful labellings, harmonious labellings, felicitous labellings, magic types of labellings. As known, (haired) cyclic-dragon graphs can be used to computer network models. The odd-elegant quality of (haired) cyclic-dragon graphs is proved, and the proof methods can be easily translated into algorithm. The work provides theoretical basis and feasible tools for cryptology and distinguishing research in networks.

cyclic-dragon graphs; haired cyclic-dragon graphs; odd-elegant labelling; leaf; odd-elegant graph

2017-02-16；

2017-07-23．

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163054，61363060，61662066).

孫 慧(1992-)，女，碩士生，E-mail:18919104606@163.com；姚 兵*(1956-)，男，教授，E-mail:yybb918@163.com.

1000-8608(2017)05-0531-06

O157.5

A

10.7511/dllgxb201705014