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

k-Path vertex cover in Cartesian product graphs

作　　者：索孟鸽 陈京荣[1] 张娟敏 SUO Meng-ge;CHEN Jing-rong;ZHANG Juan-min(School of Mathematics and Physics,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,China)

机构地区：[1]兰州交通大学数理学院,甘肃兰州730070

出　　处：《山东大学学报（理学版）》2022年第12期103-110,共8页Journal of Shandong University(Natural Science)

基　　金：甘肃省自然科学基金资助项目(1610RJZA038)。

摘　　要：对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。For a graph G and a positive integer k, a subset S?V(G) is called a k-path vertex cover if any path of order k in G contains at least one vertex from S. The cardinality of the minimum k-path vertex cover is called the k-path vertex cover number of graph G, denoted by ψk(G). The k-path vertex cover problem of Cartesian product graphs in cycle graph and cycle graph, cycle graph and complete graph, cycle graph and complete bipartite graph is studied, and the exact value, upper or lower bound of ψk(G) is obtained.

关 键 词：k-路点覆盖 笛卡尔乘积图 圈图 完全图 完全二部图 

分 类 号：O157.5[理学—数学]