On the k-path vertex cover of some graph products

被引:27
|
作者
Jakovac, Marko
Taranenko, Andrej [1 ]
机构
[1] Univ Maribor, Fac Nat Sci & Math, SI-2000 Maribor, Slovenia
关键词
k-path vertex cover; Vertex cover; Dissociation number; Independence number; Graph products; INDEPENDENCE NUMBER; DISSOCIATION NUMBER; BIPARTITE GRAPHS; TERMS;
D O I
10.1016/j.disc.2012.09.010
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order kin G contains at least one vertex from S. Denote by psi(k)(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for psi(k) of the Cartesian and the strong product of paths are derived. It is shown that for psi(3) those bounds are tight. For the lexicographic product bounds are presented for psi(k), moreover psi(2) and psi(3) are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:94 / 100
页数:7
相关论文
共 50 条
  • [31] K-PATH EULER GRAPHS
    TARWATER, JD
    WHITMORE, RW
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 1973, 23 (03) : 413 - 418
  • [32] On the k-path partition of graphs
    Steiner, G
    THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) : 2147 - 2155
  • [33] Recognizing k-path graphs
    Prisner, E
    DISCRETE APPLIED MATHEMATICS, 2000, 99 (1-3) : 169 - 181
  • [34] On k-Path Covers and their applications
    Stefan Funke
    André Nusser
    Sabine Storandt
    The VLDB Journal, 2016, 25 : 103 - 123
  • [35] Concatenated k-Path Covers
    Beck, Moritz
    Lam, Kam-Yiu
    Ng, Joseph Kee Yin
    Storand, Sabine
    Zhu, Chun Jiang
    2019 PROCEEDINGS OF THE MEETING ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2019, : 81 - 91
  • [36] Path Vertex Cover Number of Some Product Graphs
    Liu, Yan
    Deng, Xingchao
    JOURNAL OF INTERCONNECTION NETWORKS, 2024,
  • [37] On k-Path Covers and their Applications
    Funke, Stefan
    Nusser, Andre
    Storandt, Sabine
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2014, 7 (10): : 893 - 902
  • [38] A 5k-vertex kernel for 3-path vertex cover
    Xiao, Mingyu
    Kou, Shaowei
    THEORETICAL COMPUTER SCIENCE, 2023, 959
  • [39] On k-Path Covers and their applications
    Funke, Stefan
    Nusser, Andre
    Storandt, Sabine
    VLDB JOURNAL, 2016, 25 (01): : 103 - 123
  • [40] ON k-PATH PANCYCLIC GRAPHS
    Bi, Zhenming
    Zhang, Ping
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (02) : 271 - 281