图的全-Domination染色

Total-Domination Coloring of Graphs

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

A total-domination coloring of a graph G is a proper vertex coloring such that each vertex of G dominates except v at least one color class and each color class of G is dominated by at least one vertex.The minimum number of colors required for a total-domination coloring of G is called the total-domination chromatic number of G,denoted byχ_(td)(G).In this paper,this determines whetherχ_(td)(G)=k is NP-complete for any graph G and any fixed integer k≥1 through the construction of the graph and the paper studies the relationship ofχ_(td)(G)andχ_(td)(G′),where G′is a graph obtained from G through some operation.