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

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

關(guān)于樹(shù)(圖)的單點(diǎn)空間

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

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

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

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

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

1 預(yù)備知識(shí)

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

若無(wú)特別聲明,論及的圖均指有限、無(wú)向、簡(jiǎn)單圖。沒(méi)有定義的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)[18]。

對(duì)于整數(shù)n＞m≥0,為方便敘述,記[n,m]＝{m,m＋1,m＋2,…,n}。對(duì)于偶數(shù)l＞k≥0,[k,l]e＝{k,k＋2,k＋4,…,l}表示偶數(shù)集;對(duì)于奇數(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有一個(gè)集合F(G)＝{G|G二部分圖},若:

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

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

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

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

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

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

則稱L(G)為G的全魔幻空間,記為L(zhǎng)mt(G);稱(s,t)為魔幻全標(biāo)號(hào)g的魔幻常數(shù)。

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

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

(ⅱ)圖G的任何一個(gè)優(yōu)美標(biāo)號(hào)滿足f∈L(G),

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

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

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

(ⅱ)圖G的任何一個(gè)奇優(yōu)美標(biāo)號(hào)滿足f∈L(G),

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

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

定理1設(shè)圖H,T∈F,如果標(biāo)號(hào)f∈Lmt(T),點(diǎn)(g(x),g(y))∈Γ(H),則標(biāo)號(hào)g∈Lmt(H)。

證明由條件f∈Lmt(T),(f(xi),f(yj))∈Γ(T);相應(yīng)地,標(biāo)號(hào)f的拷貝f′,使得(f′(x′i),f′(y′j))∈Γ(T?)。g為H的一個(gè)標(biāo)號(hào)函數(shù),對(duì)于邊xy∈E(T)?E(H)和邊u′v′∈E(T?)?E(H),注意到點(diǎn)(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的對(duì)應(yīng)邊x′y′∈E(T?)?E(H),且uv∈E(T)?E(H)是u′v′的對(duì)應(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的對(duì)偶標(biāo)號(hào)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,點(diǎn)(u,v)∈P(s,t)。如果g∈Lb－odd(H),則圖H有標(biāo)號(hào)f滿足:

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

證明(ⅰ)設(shè)V1＝{xi|i∈[1,s]},V2＝{yj|j∈[1,t]}。f為H的一個(gè)標(biāo)號(hào)函數(shù),注意到有點(diǎn)(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的一個(gè)標(biāo)號(hào)函數(shù),注意到有點(diǎn)(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é)語(yǔ)

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

(2)問(wèn)題:①如果g∈Lb－odd(H)(或f∈Lmt(H)、或f∈Lb－g(G)),則f是否為幸福(或頂點(diǎn))標(biāo)號(hào)?

②若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.

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

姚明(1962-),男,江蘇揚(yáng)州人,副教授,研究方向?yàn)閳D的著色和標(biāo)號(hào)及計(jì)算優(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)于樹(shù)(圖)的單點(diǎn)空間[J].甘肅科學(xué)學(xué)報(bào),2016,28(5):15-18,78.]

10.16468/j.cnkii.ssn1004-0366.2016.05.004.