星图与二部图的某些乘积图上的k-路点覆盖  

The k-path vertex cover in some products graphs of star graph and bipartite graph

作　　者：尹会玲 陈京荣[1] 苏晓艳 YIN Huiling;CHEN Jingrong;SU Xiaoyan(School of Mathematics and Physics,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,China)

机构地区：[1]兰州交通大学数理学院,甘肃兰州730070

出　　处：《山东大学学报（理学版）》2023年第6期18-24,39,共8页Journal of Shandong University(Natural Science)

基　　金：甘肃省自然科学基金资助项目(1610RJZA038)。

摘　　要：对于一个点子集S■V(G),如果图G中任意一条k路上都有至少一个点来自于S,则称集合S是图G的一个k-路点覆盖。最小的k-路点覆盖集合的阶数为图G的k-路点覆盖数,记作ψ_(k)(G)。研究了星图与二部图的笛卡尔乘积图、字典积图和直乘积图上的k-路点覆盖问题,运用枚举法以及子图的相关概念,得到了它们的最小k-路点覆盖ψ_(k)(G)值的上、下界。For a subset S■V(G),if any k-path contains at least one vertex from S,then it is called a k-path vertex cover set of the graph G.The minimum cardinality of k-path vertex cover set is called the k-path vertex cover number,which is denoted byψ_k(G).The k-path vertex cover problem is studied for Cartesian product graphs,lexicographic product graphs,directed product graphs of star graph and bipartite graph,and obtain an upper and a lower bound by enumeration and related concepts of subgraphs.

关 键 词：k-路点覆盖 星图 二部图 

分 类 号：O157.5[理学—数学]