笛卡尔乘积图的k-路点覆盖

作者：索孟鸽; 陈京荣^*; 张娟敏

来源：山东大学学报(理学版), 2022, 57(12): 103-110.

• k-路点覆盖
• 笛卡尔乘积图
• 圈图
• 完全图
• 完全二部图

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点，那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖，得到ψk(G)相关的精确值和上下界。

• 单位
  兰州交通大学; 数理学院