The matching interdiction problem in dendrimers

Abstract

The purpose of the matching interdiction problem in a weighted graph is to find two vertices such that the weight of the maximum matching in the graph without these vertices is minimized. An approximate solution for this problem has been presented. 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, it is shown that proportion of difference of two optimal and approximate answers from the weight of maximum matching in these dendrimers is equal to the maximum value.