Groupe d’études et de recherche en analyse des décisions

Maximum and Minimum Number of Stable Sets for Given Order and Stability Number

Hadrien Mélot Université de Mons, Belgique

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this talk, we present tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs, connected graphs and trees. It appears that Turan graphs and a connected variant of them are extremal for these particular problems.

A simple lower bound for the Fibonacci index in terms of the stability number and the order is known and is tight for general and connected graphs. However, this bound is not tight for trees. We present extremal trees that consist of balanced stars linked together. However, an open problem is to understand how these stars are linked together. Interestingly, the golden ratio plays an important role in the proofs.

Finally, we explain briefly how the GraPHedron framework was applied to discover these results. Also, we mention how this methodology has allowed to establish all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of given order.