JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (6): 18-24, 39.doi: 10.6040/j.issn.1671-9352.0.2021.420

Previous Articles     Next Articles

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)

281

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

CLC Number: 

  • 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] LI Ning, GU Hai-bo, MA Li-na. Existence of solutions for boundary value problems of a class of nonlinear Caputo type sequential fractional differential equations on star graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(7): 22-34.
[2] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[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] GAO Chao, HOU Xin-min*. Some remarks on maximum size of bipartite graphs with a given domination number [J]. J4, 2013, 48(8): 21-23.
[6] CHEN Hong-yu1,2, ZHANG Li3. Maximum number of edges in connected bipartite graphs with  a given domination number [J]. J4, 2012, 47(8): 11-15.
[7] YANG Lin1, SUN Lei2*. Some ［r,s,t］-chromatic number of graphs [J]. J4, 2012, 47(6): 80-82.
[8] LI Zhen-lin, LU Jun-long, L Xin-zhong. On signed edge total domination of graphs [J]. J4, 2012, 47(6): 83-86.
[9] CAO Lei1,2, GUO Jia-feng1, CHENG Xue-qi1. Bipartite graph based semi-supervised method for entity mining from the query log [J]. J4, 2012, 47(5): 32-37.
[10] DING Lu-shun, YAN Jin. he Z3-connectivity for 3-regular graph [J]. J4, 2012, 47(12): 22-24.
[11] LI Ze-peng1, WANG Zhi-wen2, CHEN Xiang-en1*. Adjacent-vertex-distinguishing total coloring of planar bipartite graphs [J]. J4, 2011, 46(4): 4-8.
[12] LU Jian-li, CAI Wen-juan. The number of vertex-disjoint 6-cycles containing specified vertices in a balance bipartite graph [J]. J4, 2010, 45(12): 5-11.
[13] JU Jing-Song, LI Shuo, YANG Xin-Gang. Degree conditions for bipartite graphs to contain 6-cycles [J]. J4, 2009, 44(8): 13-15.
[14] . Vertex distinguishing IEtotal chromatic numbers of  complete bipartite graph K5,n [J]. J4, 2009, 44(2): 91-96.
[15] . On the spectrum of matching forcing numbers for bipartite graphs [J]. J4, 2009, 44(12): 30-35.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[2] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[3] DONG Li-hong1,2, GUO Shuang-jian1. The fundamental theorem for weak Hopf module in  Yetter-Drinfeld module categories[J]. J4, 2013, 48(2): 20 -22 .
[4] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[5] YANG Yong-wei1, 2, HE Peng-fei2, LI Yi-jun2,3. On strict filters of BL-algebras#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 63 -67 .
[6] LI Min1,2, LI Qi-qiang1. Observer-based sliding mode control of uncertain singular time-delay systems#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 37 -42 .
[7] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[8] TIAN Xue-gang, WANG Shao-ying. Solutions to the operator equation AXB=C[J]. J4, 2010, 45(6): 74 -80 .
[9] HUO Yu-hong, JI Quan-bao. Synchronization analysis of oscillatory activities in a biological cell system[J]. J4, 2010, 45(6): 105 -110 .
[10] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd