關于L圖的運算研究

姚明 姚兵

摘要：定義圖與標號，給出標號的可算法化的算法，得到大規模快速地構造圖的方法，為快速大規模構造圖形和方便實際應用在理論上有了依據。

關鍵詞：asrc;rolg;;graphs;;;stl;

中圖分類號：O157.5 文獻標識碼：A 文章編號：1007-9416（2020）01-0100-02

1 預備知識

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

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

1.1 定義1

給定正數。設圖是一條路，有頂點 ;路圖有頂，且有拷貝，頂點;， ;頂點分別與頂點 對應，頂點分別與頂點對應，若將對應的每對頂點均用一條邊連接;再用一條邊連接頂點與頂點，則稱所得到的圖為圖，記集合。

1.2 定義2[7-8]

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

1.3 定義3

設頂點為，的圖有，，令，則稱為圖G的中心。

2 主要結果及證明

2.1 定理

令為全體整數集合，。設圖的標號，，;若（1）當時，存在固定的常數與數，使得;（2）當時，存在，使得;則。

2.2 證明

由定義1，設圖有標號，邊集為 ，;，;頂點集為，;其中 ;讓 ，，，;將每對對應點： ，;分別用一條邊連接，最后用一條邊連接頂點與，所得到的圖為圖。

以下構造函數并證明，為敘述方便，設，，，。

3 結語

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

參考文獻

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