
doi: 10.37236/3679
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.
stability equivalence, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph polynomials, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), stability polynomial, chromatic polynomial, certificate, s-factorisation
stability equivalence, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph polynomials, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), stability polynomial, chromatic polynomial, certificate, s-factorisation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
