| 笛卡尔乘积图里的最小k-路点覆盖 |
| |
| 引用本文： | 尹会玲,郝斌斌,苏晓艳,陈京荣.笛卡尔乘积图里的最小k-路点覆盖[J].数学研究及应用,2021,41(4):340-348. |
| |
| 作者姓名： | 尹会玲 郝斌斌 苏晓艳 陈京荣 |
| |
| 作者单位： | 兰州交通大学数理学院, 甘肃 兰州 730070;兰州交通大学交通运输学院, 甘肃 兰州 730070 |
| |
| 基金项目： | 国家自然科学基金 (Grant Nos.61463026; 61463027). |
| |
| 摘 要： | 对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.
|
| 关 键 词： | $k$-路点覆盖 笛卡尔乘积图 界. |
| 收稿时间： | 2020/11/27 0:00:00 |
| 修稿时间： | 2021/4/7 0:00:00 |
Minimum $k$-Path Vertex Cover in Cartesian Product Graphs |
| |
| Huiling YIN,Binbin HAO,Xiaoyan SU,Jingrong CHEN.Minimum $k$-Path Vertex Cover in Cartesian Product Graphs[J].Journal of Mathematical Research with Applications,2021,41(4):340-348. |
| |
| Authors: | Huiling YIN Binbin HAO Xiaoyan SU Jingrong CHEN |
| |
| Institution: | School of Mathematics and Physics, Lanzhou Jiaotong University, Gansu 730070, P. R. China;School of Traffic and Transportation, Lanzhou Jiaotong University, Gansu 730070, P. R. China |
| |
| 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. |
| |
| Keywords: | $k$-path vertex cover Cartesian product graphs bound |
|
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
