图的全-Domination染色

• 作者: 王彩云
• 来源期刊: 安徽师范大学学报（自然科学版）
• 学科: 其他
• 关键词: 全控制集 染色 全-Domination染色 图操作
• 年，卷（期）: 2022,（1）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 23-28
• 页数: 6页
• 分类号: O5|C05|C12|C76
• 语种: 中文
• DOI: 10.14182/J.cnki.1001-2443.2022.01.005

摘要

图G的一个全-domination染色是图G的一个正常点染色,使得G的每个顶点v控制除了v以外的至少一个色类,并且每一个色类被G中至少一个顶点控制.图G的全-domination染色所需的最少颜色数称为G的全-domination色数,记为χtd(G).本文通过图构造的方法证明了对于任意的图G和任意固定的整数k≥1,决定χtd(G)=k是否是NP-完全的,并研究了χtd(G)和χtd(G')之间的关系,这里G'是G通过某种操作得到的图.