圖的染色和控制集問題的理論和算法研究

《圖的染色和控制集問題的理論和算法研究》是依託華東師範大學，由呂長虹擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的染色和控制集問題的理論和算法研究
• 項目類別：面上項目
• 項目負責人：呂長虹
• 依託單位：華東師範大學

項目摘要

圖染色一直是圖論研究的主流問題，在理論和套用方面均有其積極意義。圖的控制集問題及其各種推廣形式是目前圖論研究發展最快的領域之一。圖的染色和控制集問題均與圖的結構具有密切聯繫,其研究主要涉及到組合圖論方法,隨機方法,代數方法,線性規劃以及由此產生的各種算法。本項目主要考慮各種形式的染色問題和控制集問題的性質和算法。主要內容有：一，圍繞 M.Karonski等人在 2004年提出的猜想,對一般圖或特殊圖類vertex-coloring edge-weightings及相關問題的參數進行估計,包括極圖的刻畫等；二，採用組合手段,代數和隨機方法,結合新的first-fit思想，對L(j,k)-labling等問題提供一些新的技術和想法；三，考慮chordal graphs及其子圖類上各種控制集問題的有效算法。

結題摘要

圖的距離標號問題是圖的經典染色問題的推廣，也與頻率分配問題有關。本項目研究圖的L(2,1)-標號數和路覆蓋數。我們給出了樹和樹狀圖路覆蓋數的許多結果，給出了線性時間算法發現樹滿足其補圖具有唯一island sequence。我們的工作推廣了S.S. Adams等人2010年的主要工作，同時回答了J.P. Georges和 D.W. Mauro 2005年提出的公開問題。 控制集問題是運籌學中選址問題的自然模型。由於各種套用的需要，各種各樣的控制集問題被人們研究。本項目考慮r-locating-domination set, r-identifying code, paired-domination, restrained domination等問題. （1）對r-identifying codes問題， D.L. Roberts 和 F.S. Roberts 在2008年(見[5])給出了r = 2時路和圈的完整結果。我們對一般的正整數r給出了完整結果。對於2-locating- dominating sets 問題，N. Bertrand 等人在2004年(見[6])給出部分結果,我們同樣給出完整結果。 （2）對block graphs和interval graphs的paired -domination problem進行研究，給出其線性時間算法,同時我們證明了split graphs的paired -domination problem是NP-complete的。在此基礎上我們又給出paired-domina tion problem在strongly chordal graphs上線性時間算法。 （3）證明平面圖和分裂圖問題是NP-complete; 同時又證明了對即使對最大度不超過3的圖而言,restrained domination 問題也APX-complete。 本項目也證明了張鎮華教授1989年提出關於（t,n）-family中SDR數目的一個猜想。