孫 慧， 姚 兵*,2

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

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

孫 慧1， 姚 兵*1,2

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

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

圈龍圖；多毛圈龍圖；奇優(yōu)雅標號；葉子；奇優(yōu)雅圖

0 引 言

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

1 定 義

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

一個(p，q)-圖G是指V(G)=p和E(G)=q．圖G的一個從頂點集V(G)(或邊集E(G)，或全集V(G)∪E(G))到一個非負正數(shù)集的單射f是指任何2個不同頂點u、v(或2條邊或2個元素)的像不同，即f(u)≠f(v)，稱f為G的一個標號(labelling)．以下頂點標號集合{f(u)|u∈V(G)}簡記為f(V(G))，邊標號集合{f(uv)|uv∈E(G)}簡記為f(E(G))．

定義1[8,16]對于給定的(p，q)-圖G，如果存在一個單射f：V(G)→[0，q]，使得邊標號集合f(E(G))={f(uv)=f(u)-f(v)|uv∈E(G)}=[1，q]，則稱f是G的一個優(yōu)美標號(graceful labelling)，也稱G為優(yōu)美圖(graceful graph)．此外，若圖G是具有頂點二部劃分(X，Y)的二部圖，且f滿足max{f(x)|x∈X}

定義2對于給定的(p，q)-圖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的一個奇優(yōu)美標號(odd-graceful labelling)．若圖G是具有頂點二部劃分(X，Y)的二部圖，且f滿足f(X)

定義3[10]對于給定的(p，q)-圖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，則稱G為奇優(yōu)雅圖(odd-elegant graph)，f是G的一個奇優(yōu)雅標號(odd-elegant labelling)．

圖1 圈龍圖

2 主要結論

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

□

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

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

當i∈[2，n]時

f(ui，2k)=F(i+1)+2k-2n+2i-1；k∈[1，α(i)]

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

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

不難看出每個f(ui，2k-1)(i∈[1，n]，k∈[1，α(i)])是偶數(shù)，每個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}．注意到，當i∈[1，n]時，有f(ui，2k-1)f(w)，f(w)>f(u1，a1-2)，f(u1，2k)>f(u1，2(k-1))(k∈[2，α(1)-1])；當i∈[2，n]時，有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]，對于任意的頂點u，v，u≠v，有f(u)≠f(v)．

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

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

□

圖2是定理1的一個示例．

圖2 解釋定理1的一個例子

(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(u1)=0．定義多毛圈龍圖G*的邊標號為g(u1u1，j)=2q′+1-2j(j∈[1，l1])，其頂點標號為g(u1，j)=g(u1u1，j)-g(u1)=2q′+1-2j(j∈[1，l1])．

根據(jù)標號g的定義，有g(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)雅標號，敘述里省略“(mod 2q′)”．

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

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

根據(jù)標號g的定義，有g(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

因為

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)．故當u≠v(u，v∈V(G*))時，總有g(u)≠g(v)，g(V(G*))?[0，2|E(G*)|-1]．

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

□

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

圖3 解釋定理2的一個例子

3 結 語

本文探索了圈龍圖和多毛圈龍圖的奇優(yōu)雅性．定理1證明了圈龍圖具有奇優(yōu)雅標號，定理2證明了多毛圈龍圖也具有奇優(yōu)雅標號．進一步研究發(fā)現(xiàn)多毛圈龍圖完美地繼承了圈龍圖具有奇優(yōu)雅標號的性質．需要注意的是，本文的圈龍圖的圈Ci和Ci+1的連接點不能夠任意，那么連接點任意的圈龍圖的圖是否也具有奇優(yōu)雅標號呢?另外，多毛圈龍圖是通過對圈龍圖加葉子得來的，并且良好地繼承了圈龍圖具有奇優(yōu)雅標號的性質，那么這種加葉子的方法是不是可以應用于所有的圖，并且新圖是否依然繼承了原圖的標號性質，這些都是今后需要繼續(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] 姚 明,姚 兵,趙振學. 關于太陽圖魔幻標號的若干結果[J]. 甘肅科學學報, 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]. 蘭州理工大學學報, 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] 王宏宇,姚 兵,楊 超. 一類特殊對稱圖的邊魔幻性 [J]. 四川師范大學學報(自然科學版), 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] 周向前. 關于圖的優(yōu)美、奇優(yōu)美、奇優(yōu)雅標號的研究[D]. 蘭州:西北師范大學, 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．

國家自然科學基金資助項目(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