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.
机构:
Tianjin Normal Univ, Coll Math Sci, Tianjin 300071, Peoples R ChinaTianjin Normal Univ, Coll Math Sci, Tianjin 300071, Peoples R China
Liu, Yan
Deng, Xingchao
论文数: 0引用数: 0
h-index: 0
机构:
Tianjin Normal Univ, Coll Math Sci, Tianjin 300071, Peoples R China
Tianjin Normal Univ, Inst Math & Interdisciplinary Sci, Tianjin 300071, Peoples R ChinaTianjin Normal Univ, Coll Math Sci, Tianjin 300071, Peoples R China