您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (6): 18-24, 39.doi: 10.6040/j.issn.1671-9352.0.2021.420

•   • 上一篇    下一篇

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

尹会玲(),陈京荣*(),苏晓艳   

  1. 兰州交通大学数理学院, 甘肃 兰州 730070
  • 收稿日期:2021-06-09 出版日期:2023-06-20 发布日期:2023-05-23
  • 通讯作者: 陈京荣 E-mail:1553408365@qq.com;chenjr@mail.lzjtu.cn
  • 作者简介:尹会玲(1996—), 女, 硕士研究生, 研究方向为代数图论. E-mail: 1553408365@qq.com
  • 基金资助:
    甘肃省自然科学基金资助项目(1610RJZA038)

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

Huiling YIN(),Jingrong CHEN*(),Xiaoyan SU   

  1. School of Mathematics and Physics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2021-06-09 Online:2023-06-20 Published:2023-05-23
  • Contact: Jingrong CHEN E-mail:1553408365@qq.com;chenjr@mail.lzjtu.cn

RichHTML

1

PDF (PC)

274

摘要：

对于一个点子集 $S \subset V(G)$, 如果图G中任意一条k路上都有至少一个点来自于S, 则称集合S是图G的一个k-路点覆盖。最小的k-路点覆盖集合的阶数为图G的k-路点覆盖数, 记作ψk(G)。研究了星图与二部图的笛卡尔乘积图、字典积图和直乘积图上的k-路点覆盖问题, 运用枚举法以及子图的相关概念, 得到了它们的最小k-路点覆盖ψk(G)值的上、下界。

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

Abstract:

For a subset $S \subset 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.

Key words: k-path vertex cover, star graph, bipartite graph

中图分类号: 

  • O157.5
1 SELKOWS M .The independence number of graphs in terms of degrees[J].Discrete Mathematics,1993,122,343-348.
doi: 10.1016/0012-365X(93)90307-F
2 HARANTJ , SCHIERMEYERI .On the independence number of a graph in terms of order and size[J].Discrete Mathematics,2001,232,131-138.
doi: 10.1016/S0012-365X(00)00298-3
3 LIUXianliang , LUHongliang , WANGWei ,et al.PTAS for the minimum k-path connected vertex cover problem in unit disk graphs[J].Journal of Global Optimization,2013,56(2):449-458.
doi: 10.1007/s10898-011-9831-x
4 KARDOSF , KATRENICJ , SCHIERMEYERI .On computing the minimum 3-path vertex cover and dissociation number of graphs[J].Theoretical Computer Science,2011,412(50):7009-7017.
doi: 10.1016/j.tcs.2011.09.009
5 JAKOVACM , TARANENKOA .On the vertex k-path cover[J].Discrete Applied Mathematics,2013,161(13/14):19431949.
6 BREŠARB , KARDOŠF , KATRENIČJ ,et al.Minimum k-path vertex cover[J].Discrete Applied Mathematics,2011,159(12):1189-1195.
doi: 10.1016/j.dam.2011.04.008
7 JAKOVACM , TARANENKOA .On the k-path vertex cover of some graph products[J].Discrete Mathematics,2013,313(1):94-100.
doi: 10.1016/j.disc.2012.09.010
8 JAKOVACM .The $k$-path vertex cover of rooted product graphs[J].Discrete Applied Mathematics,2015,187(C):111-119.
9 张㢶㢷. 一些乘积图的k-路顶点覆盖[D]. 天津: 天津师范大学, 2016.
ZHANG Bitao. The k-path vertex cover of some product graphs[D]. Tianjin: Tianjin Normal University Press, 2016.
10 ZHANGBitao , ZUOLiancui .The k-path vertex cover of some product graphs[J].WSEAS Transactions on Mathematics,2016,15,374-384.
11 LIZhao , ZUOLiancui .The k-path vertex cover in Cartesian product graphs and complete bipartite graphs[J].Applied Mathematics and Computation,2018,331,69-79.
doi: 10.1016/j.amc.2018.03.008
[1] 李宁,顾海波,马丽娜. 星图上的一类非线性Caputo序列分数阶微分方程边值问题解的存在性[J]. 《山东大学学报(理学版)》, 2022, 57(7): 22-34.
[2] 索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[3] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[4] 李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[5] 高超,侯新民*. 关于“给定控制数的二部图的最大边数”的一点注记[J]. J4, 2013, 48(8): 21-23.
[6] 陈宏宇1,2, 张丽3. 给定控制数的连通二部图的最大边数[J]. J4, 2012, 47(8): 11-15.
[7] 杨林1,孙磊2*. 图的某些［r,s,t］-染色的色数[J]. J4, 2012, 47(6): 80-82.
[8] 李振琳,卢君龙,吕新忠. 关于图的符号边全控制[J]. J4, 2012, 47(6): 83-86.
[9] 曹雷1,2,郭嘉丰1,程学旗1. 基于二部图半监督方法的查询日志实体挖掘[J]. J4, 2012, 47(5): 32-37.
[10] 卢建立,蔡文娟. 均衡二部图中含指定顶点独立6-圈的个数[J]. J4, 2010, 45(12): 5-11.
[11] 邹青松 李硕 杨兴刚. 二部图中包含六圈的度条件[J]. J4, 2009, 44(8): 13-15.
[12] 何文玉， 陈祥恩*. 完全二部图K5,n的点可区别IE全染色[J]. J4, 2009, 44(2): 91-96.
[13] 王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.
[14] 耿建艳,颜 谨,李 峰 . 二部图中含指定顶点的独立4-圈[J]. J4, 2008, 43(5): 87-92 .
[15] 马巧灵,张苏梅 . 一类二部图的(d,1)-全标号[J]. J4, 2008, 43(2): 109-112 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
[2] 李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[3] 董丽红1,2,郭双建1. Yetter-Drinfeld模范畴上的弱Hopf模基本定理[J]. J4, 2013, 48(2): 20 -22 .
[4] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[5] 杨永伟1,2,贺鹏飞2,李毅君2,3. BL-代数的严格滤子[J]. 山东大学学报（理学版）, 2014, 49(03): 63 -67 .
[6] 李敏1,2,李歧强1. 不确定奇异时滞系统的观测器型滑模控制器[J]. 山东大学学报（理学版）, 2014, 49(03): 37 -42 .
[7] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[8] 田学刚, 王少英. 算子方程AXB=C的解[J]. J4, 2010, 45(6): 74 -80 .
[9] 霍玉洪,季全宝. 一类生物细胞系统钙离子振荡行为的同步研究[J]. J4, 2010, 45(6): 105 -110 .
[10] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发