路与圈的笛卡尔乘积的全控制数

Total Domination Numbers of Cartesian Product of Path and Cycle

令图G是无孤立点的无向图.V(G)是图G的顶点集,D是V(G)的真子集.如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集.G中最小全控制集的顶点数称为G的全控制数,记为γt(G).参考已有全控制数的知识及笛卡尔乘积Cm□Cn、Pm□Pn的全控制数的相关结论,利用γt(Cm□Cn)≤γt(Pm□Cn)≤γt(Pm□Pn)这一不等式给出了Cm□Pn(m=3,4)、Pm□Cn(n=2,4)的全控制数.

Let G be a graph without isolated vertice. A subset D？V（G） of G is a total dominating set if every vertex x∈V（G） is adjacent to at least one vertex of D. The total domination number ,denoted byγt（ G）, is the minimum cardinality of a total dominating set of G. This paper determines the total domination number of the cartesian product of Cn and Pm for any n≥2 and m∈{2,4}, or, for any m≥2 and n∈{3,4}.