Logo

Download

Title:
Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings
Authors:
Yutong Liu, Congcong Ma, Haiyuan Yao, Xu Wang
doi:
Volume
87
Issue
3
Year
2022
Pages
561-575
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.

Back