尹会玲,郝斌斌,苏晓艳,陈京荣.笛卡尔乘积图里的最小k-路点覆盖[J].数学研究及应用,2021,41(4):340~348 |
笛卡尔乘积图里的最小k-路点覆盖 |
Minimum $k$-Path Vertex Cover in Cartesian Product Graphs |
投稿时间:2020-11-27 修订日期:2021-04-07 |
DOI:10.3770/j.issn:2095-2651.2021.04.002 |
中文关键词: $k$-路点覆盖 笛卡尔乘积图 界. |
英文关键词:$k$-path vertex cover Cartesian product graphs bound |
基金项目:国家自然科学基金 (Grant Nos.61463026; 61463027). |
|
摘要点击次数: 556 |
全文下载次数: 498 |
中文摘要: |
对于子集$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. |
查看全文 查看/发表评论 下载PDF阅读器 |