关于图的符号混合控制

• 作者: 单而芳 赵衍才
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 符号混合控制函数 符号混合控制数 NP-完全 平面图 完全图
• 年，卷（期）: 2020,（6）
• 页码范围: 915-922
• 页数: 8页
• 分类号: O157.5
• 语种: 中文

摘要

设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∪Ef(x).G的符号混合控制数γs*(G)定义为G的所有符号混合控制函数的最小权.本文中,我们证明了符号混合控制问题在平面图上是NP-完全的,而且我们求出了完全图和星图的符号混合控制数的精确值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	单而芳		47	41	3.0	5.0
2	赵衍才		1	0	0.0	0.0