Certificates for properties of stability polynomials of graphs

Ranjie Mo¹ ; Graham Farr¹ ; Kerri Morgan¹

¹Monash University

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

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.

Détail

DOI : 10.37236/3679

Classification : 05C31, 05C69, 68Q17
Mots-clés : stability polynomial, chromatic polynomial, certificate, stability equivalence, s-factorisation