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

《山东大学学报(理学版)》 ›› 2022, Vol. 57 ›› Issue (12): 103-110.doi: 10.6040/j.issn.1671-9352.0.2021.784

• • 上一篇    

笛卡尔乘积图的k-路点覆盖

索孟鸽,陈京荣*,张娟敏   

  1. 兰州交通大学数理学院, 甘肃 兰州 730070
  • 发布日期:2022-12-05
  • 作者简介:索孟鸽(1998— ),女,硕士研究生,研究方向为路覆盖优化.E-mail:1306766428@qq.com*通信作者简介:陈京荣(1975— ),女,博士,教授,研究方向为网络优化理论与算法设计.E-mail:chenjr@mail.lzjtu.cn
  • 基金资助:
    甘肃省自然科学基金资助项目(1610RJZA038)

k-Path vertex cover in Cartesian product graphs

SUO Meng-ge, CHEN Jing-rong*, ZHANG Juan-min   

  1. School of Mathematics and Physics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Published:2022-12-05

PDF (PC)

106

摘要： 对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S⊆V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。

关键词: k-路点覆盖, 笛卡尔乘积图, 圈图, 完全图, 完全二部图

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.

Key words: k-path vertex cover, Cartesian product graph, cycle graph, complete graph, complete bipartite graph

中图分类号: 

  • O157.5
[1] BRESAR B, KARDOS F, KATRENIC J, et al. Minimum k-path vertex cover[J]. Discrete Applied Mathematics, 2011, 159(12):1189-1195.
[2] BRESAR B, KARDOS F, KATRENIS J, et al. On the vertex k-path cover[J]. Discrete Applied Mathematics, 2013, 161(13-14): 1943-1949.
[3] NOVOTNY M. Design and analysis of a generalized canvas protocol[C] //Proceedings of the 4th IFIP WG 11.2 International Conference on Information Security Theory and Practices: Security and Privacy of Pervasive Systems and Smart Dervices, Berlin Heidelberg: Springer-Verlag, 2010: 106-121.
[4] TU Jianhua, ZHOU Wenli. A factor 2 approximation algorithm for the vertex cover P3 problem[J]. Information Processing Letters, 2011, 111(14): 683-686.
[5] TU Jianhua, YANG Fengmei. The vertex cover P3 problem in cubic graphs[J]. Information Processing Letters, 2013, 113: 481-485.
[6] JAKOVAC M, TARANENKO A. On the k-path vertex cover of some graphs products[J]. Discrete Mathematics, 2013, 313: 94-100.
[7] JAKOVAC M. The k-path vertex cover of rooted product graphs[J]. Discrete Applied Mathematics, 2015, 187: 111-119.
[8] 张弼弢.一些乘积图k-路顶点覆盖[D].天津:天津师范大学,2016. ZHANG Bitao. The k-path vertex cover of some product graphs[D]. Tianjin: Tianjin Normal University, 2016.
[9] LI Zhao, ZUO Liancui. The k-path vertex cover in Cartesian product graphs and complete bipartite graphs[J]. Applied Mathematics and Computation, 2018, 331: 69-79.
[10] ROSENFELD V. The independence polynomial of rooted products of graphs[J]. Discrete Applied Mathematics, 2010,158:551-558.
[11] YANNAKAKIS M. Node-deletion problem on bipartite graphs[J]. SIAM Journal on Computing, 1981, 10(2): 310-327.
[12] BOLIAC R, CAMERON K, LOZIN V V. On computing the dissociation number and the induced matching number of bipartite graphs[J]. ARS Combinatoria, 2004, 72: 241-253.
[13] ORLOVICH Y, DOLGUI A, FINKE G, et al. The complexity of dissociation set problems in graphs[J]. Discrete Applied Mathematics, 2011, 159(13): 1352-1366.
[14] KARDOS F, KATRENIC J, SCHIERMEYER I. On computing the minimum 3-path vertex cover and dissociation number of graphs[J]. Theoretical Computer Science, 2011, 412(50):7009-7017.
[1] 邓梓健,刘彬,火博丰. 一类均匀拟阵的二阶圈图连通性及哈密顿性[J]. 《山东大学学报(理学版)》, 2022, 57(5): 92-96.
[2] 谭钧铭,强会英,王洪申. 单圈图的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2022, 57(2): 78-83.
[3] 张生桂,陈祥恩. 近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(5): 23-25.
[4] 王笔美,李敬文,顾彦波,邵淑宏. 单圈图的边幻和全标号[J]. 《山东大学学报(理学版)》, 2020, 55(9): 42-50.
[5] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[6] 李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[7] 杨陈, 马海成. 两类特殊三圈图的正负惯性指数和零度[J]. 山东大学学报（理学版）, 2015, 50(02): 32-37.
[8] 李振琳,卢君龙,吕新忠. 关于图的符号边全控制[J]. J4, 2012, 47(6): 83-86.
[9] 蔡华, 苗杰. n阶单圈图的边平均Wiener指标[J]. J4, 2012, 47(10): 70-74.
[10] 周旭冉, 王力工*. 一类双圈图的两种指标的排序[J]. J4, 2011, 46(11): 44-47.
[11] 袁秀华. 完全图的全符号控制数[J]. J4, 2010, 45(8): 43-46.
[12] 刘海英 马成刚 王志平. 刺图乘积上的Graham猜想[J]. J4, 2009, 44(8): 25-30.
[13] 袁秀华. 图的符号边全控制数[J]. J4, 2009, 44(8): 21-24.
[14] 何文玉， 陈祥恩*. 完全二部图K5,n的点可区别IE全染色[J]. J4, 2009, 44(2): 91-96.
[15] 刘晓妍. ［s,t］-图泛圈性的一个充分条件[J]. J4, 2008, 43(12): 28-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发