图的全-Domination染色

摘要

图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通过某种操作得到的图。