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

Minimum $k$-Path Vertex Cover in Cartesian Product Graphs

中文关键词:  $k$-路点覆盖  笛卡尔乘积图  界.

英文关键词:$k$-path vertex cover  Cartesian product graphs  bound

中文摘要:

      对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.

英文摘要:

      For the subset $S\subseteq V(G)$, if every path with $k$ vertices in a graph $G$ contains at least one vertex from $S$, we call that $S$ is a $k$-path vertex cover set of the graph $G$. Obviously, the subset is not unique. The cardinality of the minimum $k$-path vertex cover set of a graph $G$ is called the $k$-path vertex cover number, we denote it by $\psi_k(G)$. In this paper, a lower or upper bound of $\psi_k$ for some Cartesian product graphs is presented.