Genetic Algorithm for Finding the Global Forcing‎ ‎Number‎ ‎of‎ ‎Bipartite‎ ‎Graphs

Abstract

‎Consider a graph $G=(V(G),E(G))$‎, ‎where a perfect matching in $G$ is defined as a subset of independent edges with $\frac{|V(G)|}{2}$ elements‎. ‎A global forcing set is a subset $S$ of $E$ such that no two disjoint perfect matchings of $G$ coincide on it‎. ‎The minimum cardinality of global forcing sets of $G$ is called the global forcing number (GFN for short)‎. ‎This paper addresses the NP-hard problem of determining the global forcing number for perfect matchings‎. ‎The focus is on a Genetic Algorithm (GA) that utilizes binary encoding and standard genetic operators to solve this problem‎. ‎The proposed algorithm is implemented on some chemical graphs to illustrate the validity of the algorithm‎. ‎The solutions obtained by the GA are compared with the results from other methods that have been presented in the literature‎. ‎The presented algorithm can be applied to various bipartite graphs‎, ‎particularly hexagonal systems‎. ‎Additionally‎, ‎the results of the GA improve some results that‎ have already been presented for finding GFN‎.

Keywords

• perfect matching‎
• ‎global forcing set‎
• ‎genetic algorithm‎
• ‎hexagonal system‎