Counting Rules for Computing the Number of Independent Sets of a Grid Graph

Guillermo De Ita Luna (), Pedro Bello López and Raymundo Marcial-Romero
Additional contact information
Guillermo De Ita Luna: Faculty of Computer Sciences, Benemérita Universidad Autónoma de Puebla, Puebla 72570, Mexico
Pedro Bello López: Faculty of Computer Sciences, Benemérita Universidad Autónoma de Puebla, Puebla 72570, Mexico
Raymundo Marcial-Romero: Faculty of Engineering, Universidad Autónoma del Estado de México, Toluca 50000, Mexico

Mathematics, 2024, vol. 12, issue 6, 1-14

Abstract: The issue of counting independent sets of a graph, G , represented as i ( G ) , is a significant challenge within combinatorial mathematics. This problem finds practical applications across various fields, including mathematics, computer science, physics, and chemistry. In chemistry, i ( G ) is recognized as the Merrifield–Simmons (M-S) index for molecular graphs, which is one of the most relevant topological indices related to the boiling point in chemical compounds. This article introduces an innovative algorithm designed for tallying independent sets within grid-like structures. The proposed algorithm is based on the ‘branch-and-bound’ technique and is applied to compute i ( G m , n ) for a square grid formed by m rows and n columns. The proposed approach incorporates the widely recognized vertex reduction rule as the basis for splitting the current subgraph. The methodology involves breaking down the initial grid iteratively until outerplanar graphs are achieved, serving as the ’basic cases’ linked to the leaf nodes of the computation tree or when no neighborhood is incident to a minimum of five rectangular internal faces. The time complexity of the branch-and-bound algorithm speeds up the computation of i ( G m , n ) compared to traditional methods, like the transfer matrix method. Furthermore, the scope of the proposed algorithm is more general than the algorithms focused on grids since it could be applied to process general mesh graphs.

Keywords: branch-and-bound algorithm; counting independent sets; Fibonacci recurrences; grid graphs (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/6/922/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/6/922/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:6:p:922-:d:1360850

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().