| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428548 | Information Processing Letters | 2013 | 5 Pages |
•The VCP3VCP3 problem is NP-hard for cubic planar graphs of girth 3.•We give sharp lower and upper bounds on the vertex cover P3P3 number for cubic graphs.•We propose a 1.57-approximation algorithm for the VCP3VCP3 problem in cubic graphs.
A subset F of vertices of a graph G is called a vertex cover PkPk set if every path of order k in G contains at least one vertex from F . Denote by ψk(G)ψk(G) the minimum cardinality of a vertex cover PkPk set in G . The vertex cover PkPk (VCPkVCPk) problem is to find a minimum vertex cover PkPk set. In this paper, we restrict our attention to the VCP3VCP3 problem in cubic graphs. This paper proves that the VCP3VCP3 problem is NP-hard for cubic planar graphs of girth 3. Further we give sharp lower and upper bounds on ψ3(G)ψ3(G) for cubic graphs and propose a 1.57-approximation algorithm for the VCP3VCP3 problem in cubic graphs.
