The Study Of Vertex Cover K-Path Problem And The Computation Of Parameters Of Fullerene Graphs

The vertex cover k-path problem(VCPk) is to find a minimum subset of vertices such that every k-path in the graph contains at least one vertex from it. This problem is a generalization of the classic problem of vertex cover and have a wide range of applications in wireless sensor networks and the camera arrangement. The vertex cover k-path problem is an NP-hard problem. In this paper, we consider it in special graphs from the algorithm point of view. We propose a polynomial efficient algorithm for the k-path vertex cover problem in the unicyclic graphs. We also prove that the vertex cover4-path problem in cubic graphs is NP-hard and give a2-approximation algorithm.A fullerene is any molecule composed entirely of carbon, in the form of a hollow sphere, ellipsoid or tube. The discovery of fullerenes greatly expanded the number of known carbon allotropes, which until recently were limited to graphite, diamond, and amorphous carbon such as soot and charcoal. The chemical and physical properties of fullerenes have been a hot topic in the field of research and development, and are widely studied:In this paper, we consider the parameters of fullerenes and study the number of paths, independent sets and matchings of lower order in (5,6)-fullerene graphs and the number of5-matchings in (4,6)-fullerene graphs, giving the Calculation formula.