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

k-Path vertex cover in Cartesian product graphs

对于一个图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.