《圖的距離二標號問題》是依託東南大學，由林文松擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的距離二標號問題
- 項目類別：面上項目
- 項目負責人：林文松
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
圖的距離二標號是經典點著色的一個自然推廣，它在資源分配問題特別是頻道分配問題中有極其重要的套用，受到多個領域學者們的極大關注，目前已經成為國內外研究的熱點。該領域還有許多有挑戰性的問題沒有解決。本課題採用理論分析和數值實驗的方法，從理論和算法兩個方面對圖的距離二標號問題進行深入研究。探索圖的距離二標號數的行為規律以及它們所反映出的圖的結構特徵，揭示圖的距離二標號數與圖的其他參數之間的關係，設計求解一些重要圖類距離二標號數的有效算法。有望在圖的距離二圓標號、邊標號和多重標號等問題上取得重要進展。本課題的研究成果將為圖的著色理論作出貢獻，為距離標號問題的進一步研究提供基礎，開闢新的研究方向，為著色理論在頻道分配等實際問題中的套用提供理論基礎、數學模型以及相應的算法，具有重大理論意義和實際套用前景。
結題摘要
圖的染色問題是圖論中的熱點問題之一。圖的距離二標號是經典染色的自然推廣，它們在頻道分配問題中有很重要的套用。本項目對距離二標號問題進行了深入系統的研究，在幾個關鍵問題上取得了實質性進展。（1）研究圖的n重L(j,k)-標號問題,得到n重L(j,k)-標號數的基本性質以及它與其他參數的關係等，對三類格線圖基本確定了它們的n重L(j,k)-標號數和n重L(j,k)-圓標號數，一部分結果已經發表在DAM上，另一部分結果已被JOCO接受。（2）研究圖的距離二邊標號，對四類格線圖確定了它們的L(2,1)-邊標號數或給出好的上下界，這些結果已被JOCO接受。確定了無窮正則樹和低維立方體圓L(2,1)-邊標號數，結果發表在TJM上。其他一些結果發表在Ars上。（3）提出圖的組路覆蓋的概念，研究了它與圖的L(j,1)-和L(j,k)-標號數之間的關係，這些結果寫成兩篇論文已經發表在IPL上。（4）研究乘積圖的距離二標號，所得結果一部分已經發表在Ars上，一些結果則已被接受或在投稿審理階段。（5）對j不大於k的情形，確定了樹和兩個完全圖乘積的圓L(j,k)-標號數，結果發表在J.Southeast University上。（6）研究圖的多重集染色問題，解決了r方圈上的一個猜想，結果發表在IPL上；研究鄰點可區別的全染色，對三正則圖得到了很好的結果，這些結果已經投稿。以上研究成果推動了相關染色問題及其套用的研究，具有重要的理論意義和套用價值。為了使距離二標號的研究更加符合頻道分配問題的實際需要，我們提出t分離的多重L(j,k)-標號以及放鬆的距離標號等問題並展開研究，目前已經取得一些實質性結果，可望取得更大的突破和更多的創新。
