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

Document Type : Original Scientific Paper

Authors

1 ‎Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad‎, ‎‎Mashhad‎, ‎I‎. ‎R‎. ‎Iran

2 Department of Mathematics, Faculty of Basic Sciences, Velayat University

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

Main Subjects

References

[1] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, John Wiley & Sons, (2008).
[2] N. Trinajstic, Chemical Graph Theory, CRC press, 2018.
[3] F. Harary, D. J. Klein, and T. P. Živkovic, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem. 6 (1991) 295- 306, https://doi.org/10.1007/BF01192587.
[4] D. J. Klein and M. Randic, Innate degree of freedom of a graph, J. Comput. Chem. 8 (1987) 516 - 521, https://doi.org/10.1002/jcc.540080432.
[5] D. Vukicevic and M. Randic, On kekulé structures of buckminsterfullerene, Chem. Phys. lett. 401 (2005) 446 - 450,
https://doi.org/10.1016/j.cplett.2004.11.098.
[6] D. Vukicevic, S. Zhao, J. Sedlar, S.-J. Xu and T. Došlic, Global forcing number for maximal matchings, Discrete Math. 341 (2018) 801 - 809, https://doi.org/10.1016/j.disc.2017.12.002.
[7] L. Lovász and M. D. Plummer, Matching Theory, American Mathematical Soc. 367 2009.
[8] D. Vukicevic and J. Sedlar, Total forcing number of the triangular grid, Math. Commun. 9 (2004) 169 -179.
[9] D. Vukicevic and T. Došlic, Global forcing number of grid graphs, Australas. J. Combin. 38 (2007) 47 - 62.
[10] S. Klavžar, M. Tavakoli and G. Abrishami, Global forcing number for maximal matchings in corona products, Aequationes Math. 96 (2022) 997 - 1005, https://doi.org/10.1007/s00010-022-00869-3.
[11] T. Došlic, Global forcing number of benzenoid graphs, J. Math. Chem. 41 (2007) 217- 229, https://doi.org/10.1007/s10910-006-9056-2.
[12] H. Zhang and J. Cai, On the global forcing number of hexagonal systems, Discrete Appl. Math. 162 (2014) 334 - 347,
https://doi.org/10.1016/j.dam.2013.08.020.
[13] M. Sinan Oz and I. Naci Cangul, Computing the Hosoya and the Merrifield-Simmons indices of two special benzenoid systems, Iranian J. Math. Chem. 12 (2021) 161 - 174, https://doi.org/10.22052/IJMC.2021.243008.1580.
[14] Z. Yarahmadi, A note on the first geometric-arithmetic index of hexagonal systems and phenylenes, Iranian J. Math. Chem. 2 (2011) 101 - 108, https://doi.org/10.22052/IJMC.2011.5217.
[15] J. Cai and H. Zhang, Global forcing number of some chemical graphs, MATCH Commun. Math. Comput. Chem. 67 (2012) 289 - 312.
[16] P. Adams, M. Mahdian and E. S. Mahmoodian, On the forced matching numbers of bipartite graphs, Discrete Math. 281 (2004) 1 - 12, https://doi.org/10.1016/j.disc.2002.10.002.
[17] L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979) 410 - 421, https://doi.org/10.1137/0208032.
[18] K. Fukuda and T. Matsui, Finding all the perfect matchings in bipartite graphs, Appl. Math. Lett. 7 (1994) 15 -18, https://doi.org/10.1016/0893-9659(94)90045-0.
[19] S. Oskoueian, M. Tavakoli and N. Sabeghi, Finding the minimum global forcing set for maximal and perfect matchings using a greedy algorithm, Submitted.
Mathematics Interdisciplinary Research
Volume 9, Issue 4
December 2024
Pages 413-424

Files

Share

How to cite

Statistics