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

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

關(guān)于樹(圖)的單點空間

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

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

定義了全魔幻空間及優(yōu)美空間、奇優(yōu)美空間、單點空間,在空間中給出了互化標號的數(shù)學(xué)關(guān)系式,證明了標號互化可算法化,得到簡練的運算過程和標號互化結(jié)果。

單點空間;奇優(yōu)美空間;優(yōu)美空間;全魔幻空間;運算關(guān)系

Golomb[1]提出以最小整點數(shù)刻劃K個單位長的金屬棒問題,這個問題在圖論中可以用圖的標號來描述。一個圖G＝(V,E)的優(yōu)美標號是對圖G的頂點分配(0,1,2,…,|E|}中的數(shù),使得不同的頂點有不同的標號,邊的標號是其2個關(guān)聯(lián)頂點標號差的絕對值,使得邊的標號集為(1,2,…,|E|}。Rosa猜想:所有的樹都是優(yōu)美樹,猜想如果被證明,則Ringel-Kotzig猜想成立[2-4]。

1 預(yù)備知識

1970年,Rosa定義了圖G的魔幻全標號(magical total labelings,以下記為mt):對于不為零的整數(shù)s,t和一一映射f:V(G)∪E(G)→[1,p＋q],有f(x)＋f(y)＝s＋tf(xy),稱f為圖G的魔幻全標號[5,6]。一些新的圖標號和猜想己經(jīng)引起研究者的關(guān)注[7,8]。如圖G的k-魔幻標號[9,10];樹的二分優(yōu)美(bipartite graceful,以下記為b-g);二分奇優(yōu)美(bipartite odd-graceful,以下記為b-odd)[11,12]。對于圖G的一個映射f:V(G)→[0,2p－3],如果有{f(uv)|uv∈E(G)}＝[1,3,…,2p－3],則稱f為奇優(yōu)美標號[13,14];如果圖G的一個映射f:V(G)→[0,q],使得{f(uv)|uv∈E(G)}＝[1,q],稱f為優(yōu)美標號。設(shè)N為整數(shù),T是一棵n個頂點的二部分圖:即V(T)＝V1∪V2,V1∩V2＝?;V1＝{xi|i∈[1,s],s∈N}與V2＝{yj|j∈[1,t],t∈N}均為獨立集。相應(yīng)地,圖T的拷貝T?的頂點集二部分劃分為和用一條邊連接頂點u∈V(T)與頂點v∈V(T?)后所得到的圖記為H。如果圖T的一個標號f對所有的u∈V1和v∈V2,總有f(u)＜f(v),則稱f是圖T的二分標號。為敘述簡便,記這種情形f(V1)＜f(V2)。這類標號也被應(yīng)用于其他標號的研究[15-17]。迄今為止,盡管標號的研究工作在一些特殊圖類上取得了進展,但均因證明過程很少能算法化而變得困難。標號空間的定義及給定標號數(shù)學(xué)表述的應(yīng)用,結(jié)果發(fā)現(xiàn)標號互化因證明過程可算法化而得以實施,且其簡單的運算過程能夠清晰表述互化結(jié)果;除此之外,還可以規(guī)?；貥?gòu)造魔幻樹。新方法的引入為標號的研究提供了新的數(shù)理方法,能夠使得標號的研究不局限于特殊圖類,也期待能夠?qū)ρ芯績?yōu)美猜想有所幫助。

若無特別聲明,論及的圖均指有限、無向、簡單圖。沒有定義的術(shù)語和符號參見文獻[18]。

對于整數(shù)n＞m≥0,為方便敘述,記[n,m]＝{m,m＋1,m＋2,…,n}。對于偶數(shù)l＞k≥0,[k,l]e＝{k,k＋2,k＋4,…,l}表示偶數(shù)集;對于奇數(shù)t＞s≥1,令奇數(shù)集是[s,t]°＝{s,s＋2,s＋4,…,t}。記f(V(G))＝{f(x)|x∈V(G)}和f(E(G))＝{f(xy)|xy∈E(G)}。

定義1設(shè)(p,q)－圖G有一個集合F(G)＝{G|G二部分圖},若:

(ⅰ)對任意的G,T∈F,總有G∪T∈F;

(ⅱ)任何一個二部分圖G滿足G∈F,

則稱F為G的二部分圖空間。

定義2令N為全體整數(shù)集合。設(shè)圖G∈F有一個非空點集合Γ(G),對于圖G的一個標號函數(shù)f,點(f(x),f(y))∈Γ(G);若集合Γ(G)對于加法及數(shù)乘兩種運算封閉,則稱集合Γ(G)為G的點空間,特記P(s,t)＝{(s,t)|s,t∈Γ(G),s,t∈N}。

定義3令N為全體整數(shù)集合。設(shè)圖G∈F有一個集合L(G)＝{g|g:V(G)∪E(G)→[1,p＋q]}。若:

(ⅰ)對任意的g∈L(G),總存在s,t∈N,使得uv∈E(G),滿足g(u)＋g(v)＝s＋tg(uv); (ⅱ)圖G的任何一個魔幻全標號滿足f∈L(G),

則稱L(G)為G的全魔幻空間,記為Lmt(G);稱(s,t)為魔幻全標號g的魔幻常數(shù)。

定義4設(shè)集合L(G)＝{f|f:V(G)→[0,p－1],G∈F}。若:

(ⅰ)對任意的f∈L(G),使得uv∈E(G),滿足{f(uv)|uv∈E(G)}＝[1,q];

(ⅱ)圖G的任何一個優(yōu)美標號滿足f∈L(G),

則稱L(G)為G的二分優(yōu)美空間,記為Lb－g(G)。

定義5如果集合L(G)＝{f|f:V(G)→[0,2p－3],G∈F},滿足:

(ⅰ)對任意的f∈L(G),使得uv∈E(G),滿{f(uv)|uv∈E(G)}＝[0,2p－3]°;

(ⅱ)圖G的任何一個奇優(yōu)美標號滿足f∈L(G),

則稱L(G)為G的二分奇優(yōu)美空間,記為Lb－odd(G)。

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

定理1設(shè)圖H,T∈F,如果標號f∈Lmt(T),點(g(x),g(y))∈Γ(H),則標號g∈Lmt(H)。

證明由條件f∈Lmt(T),(f(xi),f(yj))∈Γ(T);相應(yīng)地,標號f的拷貝f′,使得(f′(x′i),f′(y′j))∈Γ(T?)。g為H的一個標號函數(shù),對于邊xy∈E(T)?E(H)和邊u′v′∈E(T?)?E(H),注意到點(u1,v1),(u2,v2)∈P(s,t),使得AB＝C,AM＝N成立,其中:

顯然g(u)＜g(v)。若邊xy∈E(T)?E(H)和邊u′v′∈E(T?)?E(H),滿足

則取邊xy的對應(yīng)邊x′y′∈E(T?)?E(H),且uv∈E(T)?E(H)是u′v′的對應(yīng)邊,使得

若(1－1)(g(xy)g(u′v′))T＝(0),則αω＝φ,其中:ω＝(f(xiyj)f′(u′iv′j))T。

因f的拷貝為f′,所以矛盾;根據(jù)f(ytx′1)＝2n,故S∪W∪{f(ytx′1)}＝[1,2n－1],其中:S＝{f(u)|u∈V(H)},W＝{f(uv)|uv∈E(H－ytx′1)};f(E(H))＝[1,2n－1],g∈Lmt(H)。

推論2設(shè)g∈Lmt(T);如果f∈Lmt(H),魔幻常數(shù)(k,1);則f的對偶標號f′的魔幻常數(shù)為(k′,－1),且k′＝3k。

證明由定理1,有

其中:k＝2n,(k,1)為f的魔幻常數(shù)。及

其中:k′＝6n;(k′,－1)為f′的魔幻常數(shù)。所以k′＝3k。

定理3設(shè)圖H∈F,點(u,v)∈P(s,t)。如果g∈Lb－odd(H),則圖H有標號f滿足:

(ⅰ)f∈Lmt(H);(ⅱ)f∈Lb－g(G)。

證明(ⅰ)設(shè)V1＝{xi|i∈[1,s]},V2＝{yj|j∈[1,t]}。f為H的一個標號函數(shù),注意到有點(u,v)∈P(s,t),使得

其中:k＝2n,(k,1)為f的魔幻常數(shù)。證得

(ⅱ)令u＝1＋i－n,v＝1－j,則有

由(ⅰ)證明有g(shù)(u)＜g(v),顯然f(u)＜f(v),證得f(V(H))＝[0,n－1]。注意到

由于g∈Lb－odd(H),g(E(H))＝[1,2n－3]°,所以

推論4如果f∈Lmt(H),則圖H有h滿足h∈Lb－g(G)。

證明(ⅰ)設(shè)h為H的一個標號函數(shù),注意到有點(u,v)∈P(s,t),使得

令u＝n,v＝n＋s＋2(j－1),顯然有f(u)＜f(v),從而h(u)＜h(v),證得h(V(H))＝[0,n－1]。又

由于f∈Lmt(H),f(V(H)∪E(H))＝[1,p＋q],所以h(E(H))＝{f(xy)|xy∈E(H)}＝[1,n－1],h∈Lb－g(G)。

3 結(jié)語

(1)應(yīng)用標號空間的定義及給定標號數(shù)學(xué)表達式,使得標號間關(guān)系的研究取得進展;其標號互化可算法化的數(shù)理關(guān)系及其簡便的計算方法為研究其他未知標號提供了可借鑒的研究方法。同時看到在研究中創(chuàng)新方法的引入不但使證明過程簡單、結(jié)果清晰,也有益于發(fā)現(xiàn)新結(jié)果。下步將對各種魔幻標號組建新的運算系統(tǒng),嘗試為標號的研究從理論上給出較佳的研究方法。

(2)問題:①如果g∈Lb－odd(H)(或f∈Lmt(H)、或f∈Lb－g(G)),則f是否為幸福(或頂點)標號?

②若H?F,定理1、定理2是否成立?

[1] Golomb S W.How to Number a Graph.Graph Theory and Computing[M].R.C.Read ed.,New York:Academic Press,1972.

[2] Alexander Rosa.On Certain Valuations of the Vertices of a Graph[Z].New York:Gordon and Breach,1967.

[3] Gallian J A.A Dynamic Survey of Graph Labelling[J].The Electronic Journal of Combinatorics,2012,(19):6-189.

[4] Edwards M,Howard L.A Survey of Graceful Trees[J].Atlantic Electronic Journal of Mathematics,2006,(1):5-30.

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

[6] Yao Ming,Yao Bing,Xie Jian-ming.Some Results on the K-magical Labelling of Graphs[J].Journal of Gansu Sciences,2010,(22):1-6.

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

[8] LladóA.Largest Cliques in Connected Supermagic Graphs[J].European Journal of Combinatorics,2005,(8):219-222.

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

[10] 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.

[11] Zhou Xiangqian,Yao Bing,Chen Xiang＇en,et al.A Proof to the Odd-gracefulness of All Lobsters[J].Ars Combinatoria,2012,(103):13-18.

[12] Yao Bing,Cheng Hui,Yao Ming,et al.A Note on Strongly Graceful Trees[J].Ars Combinatoria,2009,(92):155-169.

[13] Gnanajothi R B.TOpics in Graph Theory[Z].Ph.D.Thesis:Madurai Kanmaraj University,1991.

[14] Liu Xinsheng,Liu Yuanyuan,Yao Bing.Odd-gracefulness of Dragon Graphs[J].Journal of Lanzhou University of Technology,2013, (39):135-139.

[15] Yao Bing,Yao Ming,Cheng Hui.On Gracefulness of Directed Trees with Short Diameters[J].Bulletin of the Malaysian Mathematical Sciences Society,2012,(35):133-146.

[16] Zhou Xiangqian,Yao Bing,Chen Xiang＇en.Every Lobster is Odd-elegant[J].Information Processing Letters,2013,(113):30-33.

[17] 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.

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

Single Point Space of Graphs

Yao Ming1,Zhao Zhenxue1,Yao Bing2
(1.Lanzhou Petrochemical College of Vocational Technology,Lanzhou730060,China;2.College of Mathematics and Information Science,Northwest Normal University,Lanzhou730070,China)

It has defined total-magical space,graceful space,odd-graceful space and single point space in this text,in which space mathematical relationship about labeling interconversion is given,so that algorithm of labeling interconversion has been proved out,getting simple operating process and labeling interconversion result.

Single point space;Odd-graceful space;Graceful space;Total-magical space;Operating relationship

O157.5

:A

:1004-0366(2016)05-0015-05

2016-01-11;

:2016-02-19.

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

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

Yao Ming,Zhao Zhenxue,Yao Bing.Single Point Space of Graphs[J].Journal of Gansu Sciences, 2016,28(5):15-18,78.[姚明,趙振學(xué),姚兵.關(guān)于樹(圖)的單點空間[J].甘肅科學(xué)學(xué)報,2016,28(5):15-18,78.]

10.16468/j.cnkii.ssn1004-0366.2016.05.004.