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 NameAffiliation
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
Download times: 196
Abstract:
      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.
Citation:
DOI:10.3770/j.issn:2095-2651.2021.04.002
View Full Text  View/Add Comment  Download reader