The vertex cover P3P3 problem in cubic graphs

• 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.