高水平大学建设我校两青年学者解决控制集理论公开题目

本网讯 日前，图与组合优化中的两个题目：图的伴随罗马控制集题目 (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》上。

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