The independence polynomial of rooted products of graphs
A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability number \(\alpha(G)\) is the maximum size of stable sets in a graph \(G\). The independence polynomial of \(G\) is \[ I(G;x) = \sum_{k=0}^{\alpha(G)} s_kx^k= s_0+s_1x+s_2x^2+\cdots+ s_{\alpha(G)} x^{\alpha(G)} \quad (s_0:=1), \] where \(s_k\) is the number of stable sets of cardinality \(k\) in a graph \(G\), and was defined by \textit{I. Gutman} and \textit{F. Harary} [Util. Math. 24, 97--106 (1983; Zbl 0527.05055)]. We obtain a number of formulae expressing the independence polynomials of two sorts of the rooted product of graphs in terms of such polynomials of constituent graphs. In particular, it enables us to build infinite families of graphs whose independence polynomials have only real roots.
scientific article; zbMATH DE number 5703757
scientific article