The Design Of Approximation Algorithm Of The Vertex Cover Extend Problem And The Study Of Graph Invariants

Given a weighted graph, the weight of a vertex subset is defined by the sum of the vertices in this subset. If a subset of vertices satisfy each edge of the graph is incident to at least one vertex of the subset, it is named a vertex cover. The vertex cover problem is to find a minimum weight vertex cover in graph. One of main research contents is two generalizations of the classical vertex cover problem:partial vertex cover problem and prize-collecting vertex cover problem.If we just need the vertex subset covers at least k edges, then the vertex cover problem will transform into partial vertex cover problem. When the price of k equal the edge-number of graph, it is clear that the partial vertex cover problem will reduces to the vertex cover problem. Similarly, given a penalty function w on edges, the weight of a vertex subset is defined by the sum of the vertices in this subset plus the penalty of the edges not covered by this subset. Then the prize-collecting vertex cover problem is to find a vertex subset with the minimum weight. It is clear that the prize-collecting vertex cover problem will reduces to the vertex cover problem with the sufficiently large penalty function.In this paper, we, using iterative methods, in turn present an approximate algorithm for partial vertex cover problem in a given general graph with the factor of approximation is 2+, where Q is the largest finite weight in the problem definition and OPT is the optimal value for the problem, a 2-approximate algorithm for partial vertex cover problem, and a 2-approximate algorithm for prize-collecting vertex cover problem.Graph invariant, is a mapping from graph to the set of real number, which remain its value unchanged in the isomorphic graph. Some graph invariants, based on the distances between the vertices of the graph, are widely used in theoretical chemistry. In this paper, we mainly study the degree resistance distance of graph, defined as where dG (u) is the degree of vertexu of the graph G, and RG (u,v) denotes the resistance distance between the vertices wand v of the graph G. Further, we characterized the unicyclic graphs and bicyclic graphs with maximum degree resistance distance, and the cacti having minimum degree resistance distance.