姚 明，姚 兵，趙振學

(1.蘭州石化職業(yè)技術學院 信息處理與控制工程系，甘肅 蘭州 730060； 2.西北師范大學 數(shù)學與統(tǒng)計學院，甘肅 蘭州 730067)

?

一類串圖的1-維魔幻標號

姚 明1，姚 兵2，趙振學1

(1.蘭州石化職業(yè)技術學院 信息處理與控制工程系，甘肅 蘭州 730060； 2.西北師范大學 數(shù)學與統(tǒng)計學院，甘肅 蘭州 730067)

k-維(s,t)-魔幻全標號；魔幻全標號；對偶標號；全魔幻空間；向量空間

姚明,姚兵,趙振學.一類串圖的1-維魔幻標號[J].西安石油大學學報(自然科學版)，2016，31(3)：122-126.

YAO Ming，YAO Bing，ZHAO Zhengxue.1-Dimension magical lablings of string graphs[J].Journal of Xi'an Shiyou University (Natural Science Edition),2016,31(3):122-126.

引　言

1　預備知識

定義1設G是二部分(p,q)-圖，如果存在一個整數(shù)對(s,t)(s,t≠0)和一一映射f:V(G)∪E(G)→[1,p+q]，使得每一條邊xy∈E(G)，滿足f(x)+f(y)=s+tf(xy)，則稱f為圖G的一個(s,t)-魔幻全標號。圖G是(s,t)-魔幻全標號圖。此外,若(V1,V2)是G的二部劃分,且對x∈V1，y∈V2，有maxf(V1(G))

定義3令N為全體整數(shù)集合。設二部分(p,q)-圖G有一個集合P(G)={(s,t)|s,t∈N,t≠0},若

(1)對任意的一個整數(shù)對(s,t)∈P(G)，總存在G的一個一一映射f(s,t):V(G)∪E(G)→[1,p+q]，使得每條邊uv∈E(G),滿足f(s,t)(u)+f(s,t)(v)=s+tf(s,t)(uv)；

(2)圖G的任何一個(s′,t′)-魔幻全標號滿足(s′,t′)∈P(G)；

則稱P(G)為G的全魔幻空間。此外,對固定的t0≠0有全魔幻子空間P(G,t0)?P(G)。

定義4令N為全體整數(shù)集合，n，m∈N，1≤m≤n。設二部分(p,q)-圖G有一個m維向量的非空集合Γ(G)，若集合Γ(G)對于加法及數(shù)乘2種運算封閉，則稱集合Γ(G)為G的向量空間。此外,對固定的t∈N，t≠0，(s,t)∈P(G,t)?P(G)，稱Γ(G,t)?Γ(G)為G的向量子空間。

定義5設G是一個二部分(p,q)-圖G，如果存在一個映射f:V(G)→[0,2p-3]，使得f(E(G))=[1,2p-3]O，則稱f為圖G的一個奇優(yōu)美標號,稱G為奇優(yōu)美圖[12]。

例1.找(19μ,18μ+μ-1)-圖G與(25μ,24μ+μ-1)-圖R滿足定義3 的整數(shù)對(s,t)。借助計算機搜索,結(jié)果如下：

(19μ,18μ+μ-1)—圖G

(s1,t1)t1=-1(48,-1)(95,-1)(189,-1)(377,-1)(753,-1)…S1=2p+q×2n-1(s2,t2)t2=1(-9,1)(-19,1)(-39,1)(-79,1)(-159,1)…S2=1-10×2n-1?????????

(25μ,24μ+μ-1)-圖R

(s1,t1)t1=1(-10,1)(-21,1)(-43,1)(-87,1)(-175,1)…S1=1-11×2n-1(s2,t2)t2=-1(65,-1)(129,-1)(257,-1)(513,-1)(1025,-1)…S2=2p+14×2n-1+1?????????

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

由定義3,顯然有引理1：

引理1設二部分(p,q)-圖G有全魔幻空間P(G),則對固定的t∈N，t≠0有全魔幻子空間P(G,t)?P(G)，對任意的整數(shù)對(s,t)∈P(G,t)(i∈[1,m])有f(s,t),1，f(s,t),2，…，f(s,t),i。

由定義3,引理1有引理2:

證明：由引理1,對任意的整數(shù)對(si,t)∈P(G,t)(i∈[1,m])有f(s,t),1，f(s,t),2，…，f(s,t),i。由定義3，對固定的t及任意整數(shù)對(s,t)∈P(G),有f(s,t)(u)+f(s,t)(v)=s+tf(s,t)(uv)；因此s=f(s,t)(u)+f(s,t)(v)-tf(s,t)(uv)。由等式知,對固定的t，對每一個不同的f(s,t),就有一個不同的s；為敘述方便，設函數(shù)F(s,t),i=si=f(s,t)(u)+f(s,t)(v)-tf(s,t)(uv)；并令向量β，αi={si}={F(s,t),i}∈Γ(G,t)，向量組B為：α1,α2,…,αi,β。注意到

αi+1={si+1}=si+2i-1s1-2i-1={si}+2i-1{s1}-{2i-1}，

即存在整數(shù)0≠2i-1=h∈N和向量β={h}∈Γ(G,t)，使得

αi+1-αi-hα1+β=0。

根據(jù)定義4及引理1,有引理3：

引理3設二部分(p,q)-圖G有向量空間Γ(G)，并對固定的t∈N，t≠0有1

由定義2、3、4,和引理2有引理4：

引理4設二部分(p,q)-圖G有 有超級強-魔幻全標號f(s,-t)，且p≥3M=p+q+1。

(1)如果θ=s-tM，則(θ,t)∈P(G,t)，其中s，t，θ∈N，s，t，θ≠0。

(2)如果對于α(θ,t)∈Γ(G,t)，β(s0,t0)?Γ(G,t)，有α(θ,t)+tβ(s0,t0)=α(s,-t)成立,則存在最小正整數(shù)k，使得圖G為-維(θ,t)-魔幻圖,其中s0，t0∈N，s0=M，t0≥1。

證明：(1)因圖G有魔幻全標號f(s,-t)，所以(s,-t)∈P(G,t)，由引理有α(s,-t)∈Γ(G,t)。構(gòu)造G的一個標號函數(shù)g，注意到g(uv)=M-f(uv)，uv∈E(G)；g(u)=f(u)，u∈V(G)。又

g(u)+g(v)=f(u)+f(v)=s-tf(uv)=θ+tM-t(M-g(uv))=θ+tg(uv)，由定義1,3 有(θ,t)∈P(G,t)；又f(s,-t)(V(G))=[1,p]，maxf(V2(G))

(2)設(s0,t0)∈P(G,t),討論情形如下:

(1)對于α(θ,t)，因si-θi=tMi(i∈[1,m])。有

α(θ,t)={θ1,θ2,…,θm}={s1-tM1,s2-tM2,…,sm-tMm}

={s1,s2,…,sm}-t{M1,M2,…,Mm}

={s1,s2,…,sm}-t{3p1,3p2,…,3pm}

由引理3,有α(s,-t)={s1,s2,…,sm}，令β(s0,t0)={3p1,3p2,…,3pm}，這里β(s0,t0)∈Γ(G,t0)；因此

α(s,-t)+tβ(s0,t0)=α(s,-t)。

下面給出用具有1-維-魔幻全標號的二部分(p,q)-圖G來構(gòu)造大規(guī)模的1-維-魔幻全標號圖的方法和關于二部分(p,q)-圖G的1-維(s,t)-魔幻全標號的某些結(jié)果。

定理5

1:若(s,t)∈P(G)，且s′=s+tM，則(s′,-t)∈P(G)，其中M=2p+q+1，t≥1。

2:若(s,t)∈P(G)，則G有一個奇優(yōu)美標號。

證明：(1)由定義3,對于圖G的每一條邊xy∈E(G)，總有f(x)+f(y)=s+tf(xy)，因此

f(x)+f(y)=s+tf(xy)=s′-tM+tf(xy)=s′-t(f(xy)-M)。

令g(u)=f(u)(u∈V(G))，g(uv)=M-f(uv)(uv∈E(G))。對于圖G的每一條邊xy∈E(G)，有g(u)+g(v)=s′-tg(uv)。即(s,-t)∈P(G)，所以g是圖G的一個(s′,t)-魔幻全標號。

(2)設f為圖G的超級強(s,t)-魔幻全標號,不失一般性,設：f(xi)=t+i(i∈[1,s])；f(yi)=j(j∈[1,t])。從而f(E(G))=[1+p,2p-1]。注意到

φ(yi)=2p-1-2f(yi)=2p-1-2j；

注意到f(E(G))=[1+p,2p-1],即有φ(E(G))={1,3,…,2p-3}，故φ是圖G的一個奇優(yōu)美標號。

(3)設G的一個標號函數(shù)為Q，滿足：

Q(u)=p+1-f(u)(u∈V(G))，g(uv)=2p+q+1-f(uv)(uv∈E(G))。由于Q(u)+Q(v)=2(p+1)-(f(u)+f(v))

定理6若(s,-1)∈P(H)，則一致(k,m)-串圖G有(s′,-1)∈P(G)，且s′=m(s-1)+1。

證明：

步驟1.設二部分圖G1,G2,…,Gm是圖H的m個拷貝。(pi,qi)-圖Gi的頂點集二部劃分為(Xi,Yi)，其中Xi={xi,li|j∈[1,ω]}，Yi={yi,l|l∈[1,h]}，以及pi=ω+h(i∈[1,m])。xi,ω，yi,1∈V(Gi)，對于k≥1，用一條邊分別連接頂點xρ,ω∈V(Gi)與頂點yρ,1∈V(Gi+1)后所得到的圖G是(k,m)-串圖(ρ∈[1,k])。令圖G的一個標號函數(shù)Q滿足:

Q(yi,1)=(h-1)(i-1)+i；

Q(xi,ω)=(h+1)i+tm；

Q(yi,l)=Q(yi,1)+l-1；

Q(xi,j)=Q(xi,ω)-ω+j。

步驟2.設f為(p,q)-圖H的超級強(s,t)-魔幻全標號,由于f是超級的,不失一般性,設f(xj)=h+j(j∈[1,ω])，f(yr)=r(r∈[1,h])；f(xjyr)=p+q+1-θ(θ∈[1,ω+h-1])；因此f(E(H))=[1+p,2p-1]。令Q(yi,r)=r+h(i-1)，Q(xi,j)=mh+j+ω(i-1)，φ(xi,jyi,r)=2m(h+ω)-θ-(i-1)p，因此

Q(xi,j)+Q(yi,r)+Q(xi,jyi,r)

=mh+j+ω(i-1)+r+h(i-1)+2m(h+ω)-θ-(i-1)p

=h+j+r+m(p+q+1)-mθ+(m-1)(h+θ)

=f(xi)+f(yi)+mf(xiyi)+(m-1)(h+θ)

=s-f(xiyi)+mf(xiyi)+(m-1)(h+θ)

=s+(m-1)(f(xiyi)+h+θ)

=s+(m-1)(p+q+1-θ+h+θ)

=s+(m-1)(p+q+ω+1-1)

=s+(m-1)(s-1)=m(s-1)+1

令s′=m(s-1)+1,則有

Q(xi,j)+Q(yi,r)=s′-Q(xi,jyi,r)。

由定義1,3,有(s′,-1)∈P(G)，如圖1所示。

圖1　1-維魔幻標號串圖G的4個分解圖((189,-1)-邊魔幻全標號)Fig.1　Four decomposition graphs ((189,-1)-edge magic total labelling) of a 1D magical labling string graph G

3　結(jié)　語

[1]GALLIAN J A.A dynamic survey of graph labelling[J].The Electronic Journal of Combinatorics,2010(17):6-189.

[2]ALEXANDER Rosa.On Certain Valuations of the Vertices of a Graph[M].New York：Gordon and Breach,1966:349-355.

[3]ANTON Kotzig,ALEXANDER Rosa.Magic valuations of finite graphs[J].Canada Math.Bull,1970,13(4):451-461.

[4]KATHIRESAN K M.Two classes of graceful graphs[J].Ars Combinatoria,2000,55(4):129-132.

[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]Albert William.Non super edge magic total labelling[C]//Joe Ryan.The Proceeding of The 4th International Workshop on Graph Labeling.Harbin,China:Harbin Engineering University and University of Ballarat,Australia,2008:44-48.

[8]YAO Ming,YAO Bing,XIE Jianming.Some results on the k-magical labelling of graphs[J].Journal of Gansu Sciences,2010,22(1):1-6.

[9]BONDY J A,MURTY U S R.Graph Theory with Application[M].Axler S,Ribet K A,New York：MaCmillan,1976:1-629.

[10] YAO Bing,CHENG Xiangen,YAO Ming,et al.On(k,λ)-magically total labeling of graphs[J].Journal of Combinatorial Mathematics and Combinatorial Computing,2013(87):237-253.

[11] LIU Xinsheng,LIU Yuanyuan,YAO Bing.Odd-gracefulness of dragon graphs[J].Journal of Lanzhou University of Technology,2013,39(3):135-139.

[12] GALLIAN J A.A dynamic survey of graph labelling[J].The Electronic Journal of Combinatorics,2009(14):6-189.

責任編輯：張新寶

1-Dimension Magical Lablings of String Graphs

YAO Ming1，YAO Bing2，ZHAO Zhengxue1

(1.Department of Information Processing and Control Engineering,Lanzhou Petrochemical college of Vocational Technology,Lanzhou 730060,Gansu,China;2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,Gansu,China)

If there are integer paires such that a bijection of a connected graph from to satisfies for each edge,then is called a magically labeling.Furthermore,if there is minimum integer such that an abitrary-magically labeling satisfies,is called a one-dimension magically labeling.Hence,we defined the space of the magic total labellings and vector,and got 1-dimension magically labeling of the string graphs,and make use of methods of a vector algebra to research string graphs.The connections between one-dimension magically labeling and several known labelings (such as odd-graceful,dual lablings) are given.We presented a method to construct some large-scale graphs with the magic total lablings.

dimension magically total labllings;magic total lablings;dual lablings;magical total labellings space;vector space

2016-01-06

國家自然科學基金資助項目(編號：61163054)；甘肅省高等學校研究生導師科研項目(編號：1216-01)；甘肅省財政廳專項資金(編號：2014-63)

姚明(1962-),男,副教授,主要從事圖的著色和標號及計算優(yōu)化。E-mail:yybm918@163.com

10.3969/j.issn.1673-064X.2016.03.020

O157.5

1673-064X(2016)03-0122-05

A