| Autor: |
De Ita Luna, Guillermo, López, Pedro Bello, Contreras González, Meliza, Marcial Romero, José Raymundo |
| Předmět: |
|
| Zdroj: |
International Journal of Combinatorial Optimization Problems & Informatics; May-Aug2024, Vol. 15 Issue 2, p173-184, 12p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
