JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (12): 103-110.doi: 10.6040/j.issn.1671-9352.0.2021.784

Previous Articles    

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)

104

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

CLC Number: 

  • 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] YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.
[2] ZHANG Sheng-gui, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total coloring and Ⅵ-total coloring of almost complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(5): 23-25.
[3] . Vertex-distinguishing E-total coloring of complete bipartite graph K10,n with 10≤n≤90 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 23-30.
[4] LI Shi-ling, CHEN Xiang-en, WANG Zhi-wen. Vertex-Distinguishing E-Total coloring of complete bipartite graph K3,n with n≥18 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 68-71.
[5] LIU Xin-sheng, DENG Wei-dong, WANG Zhi-qiang. Several conclusions of adjacent vertex distinguishing E-total coloring of the cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 5-8.
[6] LI Zhen-lin, LU Jun-long, L Xin-zhong. On signed edge total domination of graphs [J]. J4, 2012, 47(6): 83-86.
[7] YUAN Xiu-hua. The total signed domination number of complete graph [J]. J4, 2010, 45(8): 43-46.
[8] LIU Hai-Yang, MA Cheng-Gang, WANG Zhi-Beng. Graham's conjecture on the product of the thorn graph [J]. J4, 2009, 44(8): 25-30.
[9] YUAN Xiu-Hua. Signed edge total domination numbers of graphs [J]. J4, 2009, 44(8): 21-24.
[10] ZHANG Sumei, MA Qiaoling, ZHAO Haixia. (d,1)Total labeling of the product of path and cycle graph [J]. J4, 2009, 44(4): 37-42 .
[11] . Vertex distinguishing IEtotal chromatic numbers of  complete bipartite graph K5,n [J]. J4, 2009, 44(2): 91-96.
[12] WANG Wen-li,LIU Xi-kui,ZHOU Wei . On the adjacent vertex-distinguishing incidence coloring of general Mycielski graphs [J]. J4, 2008, 43(10): 77-79 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd