笛卡尔乘积和直积图的全{k}控制划分数（英文）

作者：梁勇; 裴利丹; 胡夫涛^*; 侯新民

来源：中国科学技术大学学报, 2018, 48(08): 605-611.

• 全{k}控制划分数
• 笛卡尔乘积
• 直积

给定正整数k,不含孤立点的图G的全{k}控制函数(T{k}DF)是从顶点集V(G)到{0,1,2,…,k}的映射f使得对任意的v∈V(G),与v相邻的点在f下的赋值之和至少为k.若元素两两不同的全{k}控制函数集合{f1,f2,…,fd}满足d∑i=1fi(v)≤k对任意v∈V(G),则称该集合为G的全{k}控制族(T{k}D族).含有函数最多的G的全{k}控制族的函数数量成为全{k}控制划分数,记为dt{k}(G).2013年,Aram等提出了以下问题:是否当4nmk时dt{k}(Cm□Cn)=3,当4nmk时dt{k}(Cm□Cn)=4.这里证明了当4nmk且k≥2或4nmk且2nk时d{k}t(Cm□Cn)=3.该结论部分回答了上述问题.更进一步,确定了路和圈、路和路、圈和圈的全{k}控制划分数.

• 单位
  中国科学技术大学; 安徽大学