| 笛卡尔乘积图的k-路点覆盖 |
| |
| 引用本文： | 索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 山东大学学报(理学版), 2022, 57(12): 103-110. DOI: 10.6040/j.issn.1671-9352.0.2021.784 |
| |
| 作者姓名： | 索孟鸽 陈京荣 张娟敏 |
| |
| 作者单位： | 兰州交通大学数理学院, 甘肃 兰州 730070 |
| |
| 基金项目： | 甘肃省自然科学基金资助项目(1610RJZA038) |
| |
| 摘 要： | 对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点，那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖，得到ψk(G)相关的精确值和上下界。
|
| 关 键 词： | k-路点覆盖 笛卡尔乘积图 圈图 完全图 完全二部图 |
k-Path vertex cover in Cartesian product graphs |
| |
| SUO Meng-ge,CHEN Jing-rong,ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs[J]. Journal of Shandong University, 2022, 57(12): 103-110. DOI: 10.6040/j.issn.1671-9352.0.2021.784 |
| |
| Authors: | SUO Meng-ge CHEN Jing-rong ZHANG Juan-min |
| |
| Affiliation: | School of Mathematics and Physics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China |
| |
| Abstract: | For a graph G and a positive integer k, a subset S⊆V(G)is called a k-path vertex cover if any path of order k in G contains at least one vertex from S. The cardinality of the minimum k-path vertex cover is called the k-path vertex cover number of graph G, denoted by ψk(G). The k-path vertex cover problem of Cartesian product graphs in cycle graph and cycle graph, cycle graph and complete graph, cycle graph and complete bipartite graph is studied, and the exact value, upper or lower bound of ψk(G)is obtained. |
| |
| Keywords: | k-path vertex cover Cartesian product graph cycle graph complete graph complete bipartite graph |
|
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(理学版)》下载全文 |
