本网讯日前，图与组合优化中的两个问题：图的伴随罗马控制集问题(Arumugam、Ebadi和Manrique于2015在Indian Acad. Sci.上提出)和Cubic图的半全控制集猜想(Henning和Marcon于2016年在Annals of Combinatorics上提出)，被我校“百人计划”的两位青年教授邵泽辉和朱恩强解决。这两个问题是图的控制集理论中的公开问题，研究成果对控制集相关理论的发展起到了一定的推进作用。所得研究成果均以广州大学为第一单位发表了一系列论文。

图的伴随罗马控制集问题（Co-Roman domination）是控制集的一种变形，可应用于资源分配问题。邵泽辉教授提出了树的三种操作，通过该操作给出了伴随罗马控制的极值树的构造算法，解决了S. Arumugam等人提出的公开问题，该成果发表在国际期刊 《Discussiones Mathematicae Graph Theory》上。另外，邵泽辉教授首次将放电法（图着色理论中的一个经典研究方法）应用到图的控制集理论中，由于该方法的新颖性，该成果“On the signed Roman k-domination: Complexity and thin torus graphs”发表在知名国际期刊《Discrete Applied Mathematics》上；同时，邵泽辉教授还提出了图的独立彩虹控制集的概念，并证明了其NP完全性。 成果“Independent Rainbow Domination of Graphs”发表在国际期刊《Bulletin of the Malaysian Mathematical Society》上。

图的半全控制集是图的控制集的变形，对控制集中的顶点进行了进一步的限制，该理论相对于控制集更具应用价值。该问题被提出之后，由于其难解性，Henning和Marcon研究了不含爪的三正则图的半全控制数，他们给出了半全控制数的一个上界2n/5，并猜想n/3足矣。朱恩强教授通过分析此类图的结构和性质之间的关系，通过不同情况下的分解，巧妙地利用了二部图的完美匹配定理，证明了此猜想的最小反例含有满足猜想条件的控制集，从而给出了猜想的证明。研究成果“Semitotal Domination in Claw-Free Cubic Graphs”发表在国际权威组合杂志《Graph and Combinatorics》上。

（供稿：科研处 编辑：杨春荣）