图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通过某种操作得到的图。
科研之友
微信
新浪微博
Facebook
分享链接
