Extremal graphs for the number of independent sets on polygonal chains joined by cutting edges

Abstract

We determine extremal graphs with respect to the  number of independent sets for polygonal chains joined by cutting edges. We show that for any class of polygonal chains, independently of the number of sides on each polygon, the zig-zag polygonal chain has the extremal minimum value. Meanwhile, the polygonal chain at distance 2 between any two consecutive cutting edges provides the extremal maximum value. These results generalize and formalize previous ideas about phenylene chains.

To recognize those extremal topologies, extremal values   for the product between two Fibonacci numbers with complementary indices are determined. The product between two Fibonacci numbers with complementary indices are also applied   for recognizing extremal graphs when a path is extended with one more vertex, or when any independent subgraph is linked to the path. Our results are achieved by applying decomposition of the input graph through the vertex and edge division rules.