Computing the Forcing and Anti-Forcing Numbers of Perfect Matchings for Graphs by Integer Linear Programmings

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 C-60, C-70 and C-72, and as a consequence, the forcing and anti-forcing polynomials of them are obtained.

Automated summary

The paper proposes an efficient method - integer linear programming, to compute the forcing number and anti-forcing number of a given perfect matching in a graph. As applications, the di-forcing polynomials of C-60, C-70, and C-72 are obtained, along with their forcing and anti-forcing polynomials.