姚　明,趙振學(xué),姚　兵

(1.蘭州石化職業(yè)技術(shù)學(xué)院,甘肅 蘭州　730060;2.西北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,甘肅 蘭州　730070)

?

一類龍圖的廣義邊魔幻標(biāo)號

姚明1,趙振學(xué)1,姚兵2

(1.蘭州石化職業(yè)技術(shù)學(xué)院,甘肅 蘭州730060;2.西北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,甘肅 蘭州730070)

摘要基于研究復(fù)雜網(wǎng)絡(luò)的需要,用證明可算法化的方法分劃和構(gòu)造了一類龍圖的廣義邊魔幻標(biāo)號,證明了一個非一致龍圖存在一個集有序優(yōu)美標(biāo)號的充要條件是它有一個集有序邊魔幻標(biāo)號,給出了一類龍圖的對偶標(biāo)號。

關(guān)鍵詞邊魔幻全標(biāo)號;優(yōu)美標(biāo)號;(u,±1)-邊魔幻全標(biāo)號;對偶標(biāo)號

在編碼理論、通迅網(wǎng)絡(luò)、物流等領(lǐng)域發(fā)揮著一定作用的圖的著色和標(biāo)號,隨著計算機科學(xué)技術(shù)的發(fā)展,它們當(dāng)中的世界性難題被不斷進攻和深入的研究,因而使其成為圖論發(fā)展最活躍的分支之一。 Gallian介紹了幾十種圖的標(biāo)號和著名的猜想[1]。如1966年Ringel 猜想:即每一個完全圖k2n+1能夠被分解為2n+1個與任意一棵給定的具有n邊的樹同構(gòu)的子圖。Rosa認(rèn)為如果所有樹的都是優(yōu)美樹,則Ringel猜想成立。

1預(yù)備知識

盡管有諸多的研究工作,然而由于優(yōu)美標(biāo)號的無規(guī)律性,證明每一棵樹都是優(yōu)美樹又成為世界性的難題[2]。1970年,Kotzig等[3]定義了樹的邊魔幻全標(biāo)號并提出每一棵樹是否都是一個邊魔幻樹的問題。 一些新的圖標(biāo)號和猜想己經(jīng)引起研究者的關(guān)注[4,5],文獻[6-8]中分別提出了k-魔幻標(biāo)號和(k,λ)-魔幻全標(biāo)號。 作為研究復(fù)雜網(wǎng)絡(luò)的需要,應(yīng)用(k,λ)-魔幻全標(biāo)號于龍圖,采用分劃和構(gòu)造的方法,證明了一類龍圖具有優(yōu)美性和邊魔幻性,其證明可算法化。

若無特別聲明,論及的圖均指有限、無向、簡單圖。沒有定義的術(shù)語和符號可參見文獻[9]。對于整數(shù)n>m≥0,為敘述簡便,記[n,m]={m,m+1,m+2,…,n}。對于有p個頂點和q條邊的圖G,則說G是(p,q)-圖。對(p,q)-圖G的一個標(biāo)號f:s→[m,n],若對不同的頂點x,y∈s,有f(x)≠f(y),則稱f為G的一個正常標(biāo)號,記f(S)={f(x)|x∈S}。以下記f(V(G))={f(x)|x∈V(G)}和f(E(G))={f(xy)|xy∈E(G)}。

定義1一個(p,q)-圖G,如果存在一個整數(shù)對(μ,t)(μ,t≠0)和一個正常全標(biāo)號f:V(G)∪E(G)→[1,p+q],使得對圖G的每一條邊xy∈E(G),總有f(x)+f(y)=s+tf(xy);則稱f為圖G的一個(μ,t)-魔幻全標(biāo)號。圖G是一個(μ,t)-魔幻全標(biāo)號圖[6,8,10]。

定義3設(shè)G是一個二分(p,q)-圖G,如果存在一個正常標(biāo)號f:V(G)→[0,q],使得{f(uv)|uv∈E(G)}=[1,q],f(uv)=|f(u)-f(v)|;則稱f為圖G的一個優(yōu)美標(biāo)號,圖G是優(yōu)美圖。 此外,若max{f(x)|x∈X}

2主要結(jié)果及證明

注意到,對于每一個i∈[1,m],j∈[1,li],有g(shù)(xi,j)g(yi,t+1),且

因此有

g(xi,j)

并且

即對于每一個i∈[1,m],有

g(yi,t)≥g(yi,ni)>g(xi,li)>g(xi+1,li-1)>…>g(xi,1),

從而有g(shù)(yi,t)>g(xi,j)。綜上所述,對于任意的xi,j∈X,ys,t∈Y,有g(shù)(xi,j)

設(shè)yi,ni-ki+θ,yi+1,θ∈Y,有

g(yi,ni)=g(yi+1,ki)(θ∈[1,ki],i∈[1,m-1])

設(shè)xi,jyi,t,xi,j′yi,t′∈E(kli,ni),由g(xi,j)g(yi,t+1);g(xi,j)g(yi,t′)(或g(yi,t)

從而kli,ni和kli+1,ni+1的邊標(biāo)號集為

因此

即g為圖G 的一個集有序優(yōu)美標(biāo)號。設(shè)圖G的另一個標(biāo)號函數(shù)f滿足:

(ⅱ)f(xi,j)=g(xi,j)+1;

(ⅲ)f(xi,jyi,t)=g(xi,jyi,t)+1+q,t∈[1,ni],i∈[1,m],j∈[1,li],

其中,{kδ|δ∈[1,7]}={2,3,4,5,6,7,7},{βδ|δ∈[1,8]}={6,4,6,9,9,6,4}。

1°對于每一個i∈[1,m],由于g為圖G 的一個集有序優(yōu)美標(biāo)號,因此f(xi,j)

2°由于g(yi,ni-ki+θ)=g(yi+1,θ),i∈[1,m-1];對于θ∈[1,ki],有

f(yi,ni-ki+θ)=g(yi,ni-ki+θ)+2(ni-ki+θ)+ωi=g(yi+1,θ)+2(ni-ki)+2θ+ωi+1-2αi=g(yi+1,θ)+2θ+ωi+1=f(yi+1,θ)。

3°對任意的xi,j∈X,yi,t∈Y,xi,jyi,t∈E(kli,ni),有

4°設(shè)i=c(c≥1)時上式成立,并設(shè)f(xc,j)+f(yc,t)+f(xc,jyc,t)=μ,當(dāng)i=c+1時,有

綜上所述,f為圖G的一個(μ,-1)-集有序邊魔幻標(biāo)號。

充分性:若h為G的一個(μ,-1)-集有序邊魔幻標(biāo)號,則設(shè)標(biāo)號函數(shù)R滿足:

(ⅱ)R(xi,j)=h(xi,j)-1;

(ⅲ)R(xi,jyi,t)=h(xi,jyi,t)-1-q;t∈[1,ni],i∈[1,m],j∈[1,li]。

對于每一個i∈[1,m],由于h(xi,j)

h(yi+1,θ)-2θ+ωi+1=R(yi+1,θ)。

若xi,jyi,t,xi,j′yi,t′∈E(kli,ni),使R(xi,jyi,t)=R(xi,j′yi,t′),則有R(xi,jyi,t)+1+q=R(xi,j′yi,t′)+1+q,即h(xi,jyi,t)=h(xi,j′yi,t′),與h為G的一個(μ,-1)-集有序邊魔幻標(biāo)號矛盾,故R(xi,jyi,t)≠R(xi,j′yi,t′)。又注意到,h(E(G))=[q+2,2q+1],因此有R(E(G))=[1,q],故R為圖G的一個集有序優(yōu)美標(biāo)號,如圖1所示。

設(shè)非一致龍圖G具有一個(μ,-1)-集有序邊魔幻標(biāo)號f,f′為非一致龍圖G的另一個標(biāo)號,令

f′(u)=1+max{f(u)|u∈V(G)∪E(G)}-f(u),

由于

f′(xi,j)+f′(yi,t)+f′(xi,jyi,t)=6(q+1)-(f(xi,j)+f(yi,t)+f(xi,jyi,t))=6(q+1)-μ,

而6(q+1)-μ為常數(shù),不妨設(shè)λ=6(q+1)-μ,由定理1 中的3°、4°可知,對任意xi,j∈X,yi,t∈Y,xi,jyi,t∈E(kli,ni),均有f′(xi,j)+f′(yi,t)+f′(xi,jyi,t)=λ。因此稱f′為非一致龍圖G的對偶標(biāo)號。

定理2一個具有(μ,-1)-集有序邊魔幻標(biāo)號的非一致龍圖G存在一個(μ′,1)-魔幻標(biāo)號,其中μ′=μ-3(q+1)。

g(xi,j)=f(xi,j),g(yi,t)=f(yi,t),g(xi,jyi,t)=3(1+q)-f(xi,jyi,t)。

由于

g(yi,ni-ki+θ)=f(yi,ni-ki+θ),g(yi+1,θ)=f(yi+1,θ),

對于每一個i∈[1,m],任意的xi,j∈X,ys,t∈Y,有

f(xi,j)

因此

g(xi,j)

且對xi,jyi,t∈E(kli,ni),有f(xi,j)+f(yi,t)+f(xi,jyi,t)=μ,所以

g(xi,j)+g(yi,t)-g(xi,jyi,t)=f(xi,j)+f(yi,t)-3(q+1)+f(xi,jyi,t)=μ-3(q+1)。

若當(dāng)i=c(c≥1)時,g(xc,j)+g(yc,t)+g(xc,jyc,t)=μ-3(q+1)成立,則當(dāng)i=c+1 時,由定理1 中的3°、4° 可知,有

g(xc+1,j)+g(yc+1,t)-g(xc+1,jyc+1,t)=f(xc+1,j)+f(yc+1,t)+f(xc+1,jyc+1,t)-3(q+1)=f(xc,j)+f(yc,t)+f(xc,jyc,t)-3(q+1)=μ-3(q+1),

因此g為圖G的一個(μ-3(q+1),1)-魔幻標(biāo)號。

3結(jié)語

研究小點數(shù)龍圖的優(yōu)美性及它的廣義邊魔幻性所取得的進展,使得復(fù)雜網(wǎng)絡(luò)的研究得到了幫助,也為今后進一步的研究工作奠實了理論基礎(chǔ)。

(1)使用證明方法可算法化的方法分劃和構(gòu)造了一類優(yōu)美龍圖和一類邊魔幻全標(biāo)號龍圖,定義了一類龍圖的對偶標(biāo)號,同時探究其與其他標(biāo)號之間的關(guān)系,以期有較好的發(fā)現(xiàn)。

(2)問題:在小點數(shù)龍圖研究基礎(chǔ)上,能否找到它的頂點魔幻標(biāo)號及最大度的龍圖？

參考文獻:

[1]Joseph A Gallian.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics,2007,14:6-189.

[2]Enomoto H,Llado A S,Nakamigawa T,et al.Super Edge-magic Graphs[J].SUT J.Math.,1998,34:105-109.

[3]Anton Kotzig,Alexander Rosa.Magic Valuations of Finite Graphs[J].Canada.Math.Bull,1970,13:451-461.

[4]Kathiresan K M.Two Classes of Graceful Graphs[J].Ars Combinatoria,2000,55:129-132.

[5]Ladó A.Largest Cliques in Connected Supermagic Graphs[J].European Journal of Combinatorics,2005,28(8):2 240-2 247.

[6]Yao Bing,Zhang Zhongfu,Yao Ming,et al.A New Type of Magical Coloring[J].Advances in Mathmatics,2008,37(5):571-583.

[7]Yao Bing,Yao Ming.On Felicitous Labelling of Trees[C]//Joe Ryan,Mirka Miller.The Proceeding of the 4th International Workshop on Graph Labeling.Harbin:Harbin Engineering University and University of Ballarat,Australia,2008.

[8]Yao Bing,Chen Xiang-en,Yao Ming,et al.On (k,λ)-magically Total Labeling of Graphs[J].Journal of Combinatorial Mathematics and Combinatorial Computing,2013,87:237-253.

[9]Bondy J A,Murty U S R.Graph Theory with Application[M].New York:MaCmillan,1976.

[10]姚明,姚兵,謝建民.關(guān)于圖k-魔幻標(biāo)號的若干結(jié)果[J].甘肅科學(xué)學(xué)報,2010,22(1):1-6.

[11]Albert William,Bharati Rajan.Non Super Edge Magic Total Labelling[C]//Joe Ryan,Mirka Miller.The Proceeding of The 4th International Workshop on Graph Labeling.Harbin:Harbin Engineering University and University of Ballarat,Australia,2008.

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

[13]Baca M,Bertault F,MacDougall J A,et al.Vertex-antimagic Total Labellings of Graphs[J].Discuss.Math.Graph Theory,2003,23(1):67-83.

[14]Grace T.On Sequential Labelings of Graphs[J].Graph Theory,1983,2(7):195-201.

[15]Bondy J A,Murty U S R.Graph Theory with Application[M].New York:MaCmillan,1976.

Generalized Boundary Magic Label of First Class Dragon Pattern

Yao Ming1,Zhao Zhenxue1,Yao Bing2

(1.Lanzhou Petrochemical College of Vocational Technology,Lanzhou 730060,China;2.College of Mathematics and Information Science,Northwest Normal University,Lanzhou 730070,China)

Key wordsTotal boundary magic label;Graceful label;(u,±1)-Total boundary magic label;Complementary label

AbstractBased on the need of study on complex network,the generalized boundary magic label of first class dragon pattern is divided and built by the method of proving algorithmization to prove that the necessary and sufficient condition of a non-uniform dragon pattern existing graceful label of ordered set is to have a magic label of ordered set,and present the complementary label o first class dragon pattern.

doi:10.16468/j.cnki.issn1004-0366.2016.03.001.

收稿日期:2015-07-08;修回日期:2015-09-31.

基金項目:國家自然科學(xué)基金資助項目(61163054);甘肅省高等學(xué)校研究生導(dǎo)師科研項目(1216-01);甘肅省財政廳專項資金(2014-63).

作者簡介:姚明(1962-),男,江蘇省揚州人,副教授,研究方向為圖的著色和標(biāo)號及計算優(yōu)化.E-mail:yybm918@163.com.

中圖分類號:O157.5

文獻標(biāo)志碼:A

文章編號:1004-0366(2016)03-0001-05

引用格式:Yao Ming,Zhao Zhenxue,Yao Bing.Generalized Boundary Magic Label of First Class Dragon Pattern[J].Journal of Gansu Sciences,2016,28(3):1-5.[姚明,趙振學(xué),姚兵.一類龍圖的廣義邊魔幻標(biāo)號[J].甘肅科學(xué)學(xué)報,2016,28(3):1-5.]