Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings

Abstract

The forcing polynomial and anti-forcing polynomial are two important enumerative polynomials associated with all perfect matchings of a graph. In a graph with large order, the exhaustive enumeration which is used to compute forcing number of a given perfect matching is too time-consuming to compute anti-forcing number. In this paper, we come up with an efficient method — integer linear programming, to compute forcing number and anti-forcing number of a given perfect matching. As applications, we obtain the di-forcing polynomials C60 , C70 and C72 , and as a consequence, the forcing and anti-forcing polynomials of them are obtained.