The matching interdiction problem in dendrimers

ABSTRACT The purpose of the matching interdiction problem in the weighted graph G is to find a subset of vertices VR * such that the weight of the maximum matching in the graph]\ [ *RVG is minimized. According to the maximum matching in G, an approximate solution, denoted by R, for this problem is presented. Suppose that)(Gv is the weight of the maximum matching in G. In this paper, we consider dendrimers as graphs such that the weights of edges are the bond lengths. We obtain the maximum matching in some types of dendrimers. Then, we compute the value of]))\[()((]))\[()( ( * RVGvGvRVGvGv for them. It is shown that this ratio in these classes of dendrimers is equal to the maximum value