图的染色和控制集问题的理论和算法研究

图染色一直是图论研究的主流问题，在理论和应用方面均有其积极意义。图的控制集问题及其各种推广形式是目前图论研究发展最快的领域之一。图的染色和控制集问题均与图的结构具有密切联系,其研究主要涉及到组合图论方法,随机方法,代数方法,线性规划以及由此产生的各种算法。本项目主要考虑各种形式的染色问题和控制集问题的性质和算法。主要内容有：一，围绕 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数目的一个猜想。