ABSTRACT

An independent set of a graph G is a set of pairwise nonadjacent vertices. The independence polynomial fG of G is the generating function of the sequence {fs }, where f s = f s ( G ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315367996/04dcd8b6-b62e-41d4-a1ee-e2e18fb6354f/content/eq238.tif"/> is the number of independent vertex sets of cardinality s in G. That is, f G ( x ) = ∑ s = 0 α f s x s https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315367996/04dcd8b6-b62e-41d4-a1ee-e2e18fb6354f/content/eq239.tif"/> . Here, α ( G ) = α https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315367996/04dcd8b6-b62e-41d4-a1ee-e2e18fb6354f/content/eq240.tif"/> is the cardinality of the largest independent set of G. Prodinger and Tichy [19] introduced the idea of counting independent sets in graphs in 1982, calling the number of independent sets in a graph G the fibonacci number of G, and their work quickly generated attention. Applications were found in various sciences. Molecular chemists, for example, call this parameter the Merrifield–Simmons Index and have found it useful for studying molecular structures [15].