图的全-Domination染色

王彩云

(青海师范大学 数学与统计学院，西宁 810008)

1 引言与预备知识

图G的一个正常点染色是一个映射f:V(G)→{1,…,k},使得图G中的任意两个相邻顶点u,v均有f(u)≠f(v)。图G的正常点染色所需要的最小颜色数称为色数,记为χ(G)。事实上,图G的正常点染色可将图G的顶点集划分为k个独立集{V1,V2,…,Vk},这里每个独立集称为一个色类,记为Vi={v∈V(G)|f(v)=i},i=1,…,k。图G的一个l-染色是指用l种颜色对G进行的一个正常点染色。

图的染色被大量用在涉及稀缺资源分配的实际问题的模型中(例如：课程表问题)，并且它在图论、离散数学和组合优化的发展中发挥了关键作用。随着应用背景的不断拓宽,一些其他染色概念被提出来。

Gera[11]等人提出了图的domiator染色的概念。图的domiator染色是指图G中每个顶点都至少与一个色类(可能是自己的色类)里的全部顶点相邻。图G的dominator染色所需的最少颜色数称为G的dominator色数,记为χd(G)。在2012年,K.Kavitha[12]研究了星和双星图族的 Middle图、Total图和Central图的dominator色数,同时还证明了上述图族的dominator色数和星色数之间的关系。

周[15]等人在dominator染色概念的基础上提出了domination染色的概念。图G的domination染色是指G的每个顶点至少与一个色类里的全部顶点相邻并且图G的每个色类的顶点要与G中至少一个顶点相邻。图G的domination染色所需的最少颜色数称为G的domination色数,记为χdd(G)。

K.P.chithra[16]等人在dominaton染色概念的基础上提出了全-do mination染色的概念。图G的全-domination染色是指G的每个顶点至少与一个色类(除了v)里的全部顶点相邻并且图G的每个色类的顶点要与G中至少一个顶点相邻。图G的全-domination染色所需的最少颜色数目称为G的全-domination色数,记为χtd(G)。……