应用数学学报

作者：赵衍才, 单而芳

单位：1. 无锡城市职业技术学院, 江苏 214153;<br>2. 无锡环境科学与工程研究中心, 江苏 214153;<br>3. 上海大学管理学院, 上海 200444

关键词：符号混合控制函数,符号混合控制数,NP-完全,平面图,完全图

设G=（V，E）是一个顶点集为V且边集为E的简单图.G的一个符号混合控制函数定义为函数f：V∪E→{-1，1}，使得对每个元素x∈V∪E都有Σy∈Nm（x）∪{x} f（y）≥1成立.此处，Nm（x）是V∪E中与x相邻或关联的所有元素的集合.f的权为w（f）=Σx∈V∪E f（x）.G的符号混合控制数γs*（G）定义为G的所有符号混合控制函数的最小权.本文中，我们证明了符号混合控制问题在平面图上是NP-完全的，而且我们求出了完全图和星图的符号混合控制数的精确值.

来源：2020年第6期

《应用数学学报》期刊编辑部

查看应用数学学报杂志2020年第6期