# Certificates for Properties of Stability Polynomials of Graphs

Keywords:
Stability polynomial, Chromatic polynomial, Certificate, Stability equivalence, s-factorisation

### Abstract

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

*stability equivalence*, when two graphs have the same stability polynomial. We give certifications of stability equivalence for two infinite families of graphs.