Certificates for properties of stability polynomials of graphs (Q405176)

Summary: A stable (or independent) set is a set of vertices where no two of the vertices in the set are adjacent. The stability polynomial \(A(G; p)\) of a graph \(G\) is the probability that a set of randomly chosen vertices is stable where the probability of each vertex being chosen is \(p\), with choices independent. This polynomial is analogous to the chromatic polynomial in a precise sense. This paper considers factorisation of stability polynomials, following work by Morgan and Farr on factorisation of the chromatic polynomial. The stability polynomial \(A(G;p)\) is said to have an s-factorisation with s-factors \(H_{1}\) and \(H_{2}\) if \(A(G; p) = A(H_{1};p) A(H_{2};p)\). This clearly occurs when \(G\) is a disjoint union of \(H_{1}\) and \(H_{2}\). We find many other cases where such factorisation occurs even when \(G\) is connected. We find 152 different s-factorisations of connected graphs of order at most 9, and two infinite families. We introduce certificates of s-factorisation to explain s-factorisations in terms of the structure of \(G\). Short certificates for s-factorisations of connected graphs of order at most 6 are found. Upper bounds for the lengths of the certificates of s-factorisations are given. We also use certificates to explain \textit{stability equivalence}, when two graphs have the same stability polynomial. We give certifications of stability equivalence for two infinite families of graphs.