Minimum $k$-Path Vertex Cover in Cartesian Product Graphs
Received:November 27, 2020  Revised:April 07, 2021
Key Word: $k$-path vertex cover   Cartesian product graphs   bound
Fund ProjectL:Supported by the National Natural Science Foundation of China (Grant Nos.61463026; 61463027).
 Author Name Affiliation Huiling YIN School of Mathematics and Physics, Lanzhou Jiaotong University, Gansu 730070, P. R. China Binbin HAO School of Traffic and Transportation, Lanzhou Jiaotong University, Gansu 730070, P. R. China Xiaoyan SU School of Mathematics and Physics, Lanzhou Jiaotong University, Gansu 730070, P. R. China Jingrong CHEN School of Mathematics and Physics, Lanzhou Jiaotong University, Gansu 730070, P. R. China
Hits: 151
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.