Independent sets of cardinality \(s\) of maximal outerplanar graphs (Q2869891)

Let \(G\) be a simple (finite, undirected with no loops) graph and for a non-negative integer \(s\), let \(f_s(G)\) denote the number of independent sets of size \(s\) in \(G\). \textit{I. Gutman} and \textit{F. Harary} [Util. Math. 24, 97--106 (1983; Zbl 0527.05055)] called the generating function NEWLINE\[NEWLINEI(G; x) = \sum_{s \geq 0} f_s(G)x^s NEWLINE\]NEWLINE the Fibonacci polynomial of \(G\). The authors define the 2-spiral (graph) \(S_n^2\) to be \(K_1 \vee P_{n - 1}\) and \(D_6^2\) to be the unique maximal outerplanar graph on \(n \geq 6\) vertices with \(3\) vertices of degree \(2\) and prove that if \(G\) is a maximal outerplanar graph on \(n \geq 6\) vertices, then for all \(s \geq 3\), we have \(f_s(G) \leq {{n - s} \choose s}\) with equality if and only if \(G \in \{S_6^2, D_6^2\}\) when \(n = 6\) and \(G \cong S_n^2\) when \(n \geq 7\).