《圖的幾類標號問題》是依託浙江師範大學，由陳東擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的幾類標號問題
- 項目類別：青年科學基金項目
- 項目負責人：陳東
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
隨著市場經濟和無線通信事業的快速發展，無線電頻率需求量的逐漸增大與有限的無線電頻率資源之間的矛盾日益增大，使頻率分配問題成為當前亟需解決的重要課題。圖的距離2標號問題以及它的一些推廣，就是在這種背景下產生的，它們可以看做是一些特殊的染色問題，近十年來受到了國內外同行的極大關注。本項目研究圖的L(p,q)-標號、(d,1)-全標號、(d,1)-點面全標號等相關標號問題。圍繞著名的Griggs和Yeh的猜想，重點開展對樹圖L(2,1)-標號數的刻畫。致力於Havet和Yu關於圖的(d,1)-全標號的猜想，力爭能夠尋找到更多的圖類滿足該猜想，並進一步研究樹圖(2,1)-全標號數的刻畫條件。將系統地研究圖的(d,1)-點面全標號，並推廣點面全染色中的相關結果到(d,1)-點面全標號問題上。研究圖距離2圓標號、無圈邊染色、鄰點可區別全染色等相關問題。擬在三年內完成3-5篇論文，半數以上被SCI收錄。
結題摘要
隨著社會的發展，無線電技術及其套用已成為人類生產生活中必不可少的一部分。所有的無線電業務都離不開無線電頻率，但無線電頻率資源卻是有限的。因此，合理地分配無線電頻率已經成為了亟待解決重要問題。在此套用背景下，圖的L(2,1)-標號問題（即圖的距離2問題）和它的一些推廣成為了當前的熱點。樹型網路(樹圖)在網路拓撲結構中有著無可替代的地位，是中小型網路採用的主要拓撲結構，而樹圖的L(2,1)-標號數不是Δ+1就是Δ+2，因而尋找其刻畫條件就變得非常有意義。自立項以來，本項目組致力於研究該課題的研究，完成了最大度為3的樹的L(2,1)-標號數的刻畫，該成果發表於雜誌《數學學報（中文版）》。圖的(2,1)-全標號問題是L(2,1)-標號問題的一個重要推廣，樹圖在(2,1)-全標號下有著與L(2,1)-標號類似結論，其(2,1)-全標號數不是Δ+1就是Δ+2。本項目組定義了樹圖中壞點，證明了：對於最大度至少為9的樹，若不存在距離為偶數的壞點，則其(2,1)-全標號數為Δ+1。此成果發表於雜誌《Journal of Combinatorial Optimization》。本項目組還研究了距離2標號問題的另一種推廣，圖的(2,1)-點面標號問題，並取得如下成果：完全刻畫了樹、圈、歐拉二部圖、四階完全圖的(2,1)-點面標號數；給出了外平面圖(2,1)-點面標號數的緊的上下界；完全刻畫了開外平面圖以及至含有一個閉內面的外平面圖的(2,1)-點面標號數。該系列成果發表於《浙江師範大學學報（自然科學版）》。此外，本項目還研究了圖的無圈染色問題，改進了M. Montassier等學者的關於平面圖是無圈4可選的一個充分條件。證明了不含相交的3、4 或5-圈的平面圖是無圈4-可選的。本項目組總計發表相關論文9篇，其中5篇被SCI檢索。本項目的取得的這些研究成果極大地豐富了圖的標號及相關問題的研究內容。
