Abstract
A subset F of vertices of a graph G is called a vertex cover Pk set if every path of order k in G contains at least one vertex from F. Denote by ψk(G) the minimum cardinality of a vertex cover Pk set in G. The vertex cover Pk (VCPk) problem is to find a minimum vertex cover Pk set. It is easy to see that the VCP2 problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP4 problem in cubic graphs. The paper proves that the VCP4 problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ4(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.
Acknowledgement
This work was supported by the National Natural Science Foundation of China (No. 11201021). We thank the editor and the reviewers for their valuable comments that greatly helped us to improve the quality of the manuscript.