關(guān)于L圖的運(yùn)算研究

姚明 姚兵

摘要：定義圖與標(biāo)號，給出標(biāo)號的可算法化的算法，得到大規(guī)?？焖俚貥?gòu)造圖的方法，為快速大規(guī)模構(gòu)造圖形和方便實(shí)際應(yīng)用在理論上有了依據(jù)。

關(guān)鍵詞：asrc;rolg;;graphs;;;stl;

中圖分類號：O157.5 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2020）01-0100-02

1 預(yù)備知識

應(yīng)對無線電頻道分配（assigning radio channels，asrc）互不干擾問題的廣播標(biāo)號（radio labeling， rolg）基于簡單圖給出了各種研究成果，但各基站之間的關(guān)聯(lián)以及標(biāo)定標(biāo)號的結(jié)論多因所設(shè)條件計(jì)算復(fù)雜較難實(shí)際應(yīng)用[1-2]。本文定義了就研究rolg方面有代表性的圖并給出了可算法化的構(gòu)造過程，給出了魔幻廣播標(biāo)號，較細(xì)地探討了對rolg影響較深的性質(zhì)，從而使rolg增加實(shí)用范圍和應(yīng)用方便的優(yōu)點(diǎn)，具有理論參考價(jià)值。

若無特別聲明，本文中論及的圖均指有限、無向、簡單圖，沒有定義的術(shù)語和符號參見文獻(xiàn)[3]。為方便敘述，記整數(shù)集，其中。對于偶數(shù)，偶數(shù)集為;對于奇數(shù)，奇數(shù)集是。記為圖G的直徑，若、，則記為兩點(diǎn)和的距離;設(shè)集合 ，如果圖的一個(gè)標(biāo)號對任意的，，總有，則為正常標(biāo)號;此外，讓，，若，則稱為圖G的一個(gè)正常有序標(biāo)號;記集合 正常有序標(biāo)號}。圖G的一個(gè)標(biāo)號，記頂點(diǎn)集 ，邊集。若，，如果對任意的，，總有，則為圖G的一個(gè)強(qiáng)標(biāo)號（strongly labelling，簡記為stl）;記集合為stl} [4-6]，讓是一個(gè)所有與頂點(diǎn)鄰接的頂點(diǎn)集。對于任意的，有，則稱為在G圖中的層;度為1的頂點(diǎn)稱為葉子。

1.1 定義1

給定正數(shù)。設(shè)圖是一條路，有頂點(diǎn) ;路圖有頂，且有拷貝，頂點(diǎn);， ;頂點(diǎn)分別與頂點(diǎn) 對應(yīng)，頂點(diǎn)分別與頂點(diǎn)對應(yīng)，若將對應(yīng)的每對頂點(diǎn)均用一條邊連接;再用一條邊連接頂點(diǎn)與頂點(diǎn)，則稱所得到的圖為圖，記集合。

1.2 定義2[7-8]

令為全體整數(shù)集合，。設(shè)圖有標(biāo)號，。若存在，使得對任意，都有成立，則稱為的魔幻廣播標(biāo)號（Magically Radio Labelling，簡記），為的魔幻常數(shù)，G為圖;記集合。

1.3 定義3

設(shè)頂點(diǎn)為，的圖有，，令，則稱為圖G的中心。

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

2.1 定理

令為全體整數(shù)集合，。設(shè)圖的標(biāo)號，，;若（1）當(dāng)時(shí)，存在固定的常數(shù)與數(shù)，使得;（2）當(dāng)時(shí)，存在，使得;則。

2.2 證明

由定義1，設(shè)圖有標(biāo)號，邊集為 ，;，;頂點(diǎn)集為，;其中 ;讓 ，，，;將每對對應(yīng)點(diǎn)： ，;分別用一條邊連接，最后用一條邊連接頂點(diǎn)與，所得到的圖為圖。

以下構(gòu)造函數(shù)并證明，為敘述方便，設(shè)，，，。

3 結(jié)語

魔幻廣播標(biāo)號和圖的定義，圖可算法化的方法，它不僅對研究rolg的其它圖類有借鑒意義，而且在應(yīng)用上具有普適性和方便性，這使得它利于深入的研究asrc互不干擾問題，具有理論意義。若，，求定理成立的條件。

參考文獻(xiàn)

[1] Devsi Bantva.et.al.Radio number of trees[J].Electronic Notes in Discrete Mathematics，2015（48）：135-141.

[2] Xiangwen Li，Vicky Mak，Sanming Zhou.Optimal radio labellings of complete m-ary trees[J].Discrete applied mathematics，2009（158）：507-505.

[3] Bondy J.A and Murty U.S.R.Graph Theory with Application[M].S.Axler，K.A.Ribet.New York：MaCmillan，1976.

[4] Kathiresan K.M.Two classes of graceful graphs[J].Ars Combinatoria，2000（55）：129-132.

[5] J.MacDougall，M.Miller，Slamin and W.D.Wallis，Vertex-magic total labelings[J].Utilitas. Math，2002（61）：3-21.

[6] Bing Yao，Zhongful Zhang，Ming Yao，Jingwen Li.A New Type of Magical coloring[J].Advances in Mathmatics，2008（37）：571-583.

[7] Ming Yao et al.Bipartite Total Graceful Lablling of Trees[J].Journal of Lanzhou Jiaotong University，2017（36）：132-135.

[8] Joseph A.Gallian.A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics，2007（14）：6-189.