\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.66}{21(1)}{2014} %\usepackage{natbib} % Use the natbib bibliography and citation package \usepackage{graphicx} % This is used to load the crest in the title page \usepackage[english]{babel} \usepackage{url} \usepackage{amssymb} \usepackage{amsmath, amsthm} \usepackage[english]{babel} \usepackage{longtable} \usepackage[figuresright]{rotating} \usepackage{url} \newtheorem{thm}{Theorem} \newtheorem{lemma}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{fact}[thm]{Fact} \newtheorem{conj}[thm]{Conjecture} \newtheorem{problem}[thm]{Problem} \newtheorem{propn}[thm]{Proposition} \newcommand{\CP}[1]{\ensuremath{P_{#1}(\lambda)}} \newcommand{\CPJ}[2]{\ensuremath{P({#1},\lambda-{#2})}} \newcommand{\GE}[2]{\ensuremath{{#1}\sim_{\mathcal{G}}{#2}}} \allowdisplaybreaks %opening %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Certificates for properties of\\ stability polynomials of graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Ranjie Mo \hspace{6mm} Graham Farr \hspace{6mm} Kerri Morgan\\ \small Clayton School of Information Technology\\[-0.8ex] \small Monash University\\[-0.8ex] \small Melbourne, Australia\\ \small\tt \{ranjie.mo,graham.farr,kerri.morgan\}@monash.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Aug 30, 2013}{Mar 14, 2014}{Mar 24, 2014}\\ \small Mathematics Subject Classifications: 05C31, 05C69, 05E99, 68Q17} \begin{document} \maketitle \begin{abstract} A \textit{stable} (or \textit{independent}) set is a set of vertices where no two of the vertices in the set are adjacent. The \textit{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 \textit{s-factorisation} with \textit{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 \textit{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. % keywords are optional \bigskip\noindent \textbf{Keywords:} stability polynomial; chromatic polynomial; certificate; stability equivalence; s-factorisation \end{abstract} \section{Introduction} The \textit{chromatic polynomial} $P(G; \lambda)$ of a graph $G$ gives the number of different ways colours can be assigned to the vertices of a graph such that no pair of adjacent vertices get the same colour \cite{Birkhoff-1912-1913}. In this paper we will consider one of its relatives, the stability polynomial, and study its factorisation properties. Let $G$ be a graph and $p \in [0, 1]$ be the probability of each vertex being chosen. The vertex choices are made independently. The \textit{stability polynomial} $A(G;p)$ of a graph $G$ is the probability that a set of randomly chosen vertices is stable (i.e., no two adjacent) \cite{Farr-1993, Helgason-1974}. This polynomial plays the same role for graphic 2-polymatroids as the chromatic polynomial plays for graphs \cite{Helgason-1974}. Let $H_{1}$ and $H_{2}$ be graphs. The stability polynomial of graph $G$ is said to have an \textit{s-factorisation} with \textit{s-factors} $H_{1}$ and $H_{2}$ if \begin{align} \label{eqn1.2} A(G; p) = A(H_{1};p) A(H_{2};p). \end{align} The graph $G$ is said to be \textit{s-factorised} or $G$ is \textit{s-factorisable}. In this research we will focus on the s-factorisations of connected graphs because it is known that any disconnected graph always has an s-factorisation \cite{Farr-1991}. In principle, s-factorisations of graph $G$ could be used to reduce the time taken to calculate $A(G;p)$ by calculating the product of the stability polynomial of two smaller graphs $H_{1}$ and $H_{2}$. As a polynomial is an algebraic object, the study of its algebraic properties, including factorisation, is important. But there has been little research done on the factorisation of graph polynomials. Morgan and Farr \cite{Morgan-2009} pioneered the use of certificates to study the algebraic properties of chromatic polynomials. In this paper, we introduce certificates for stability polynomials, and establish some of their fundamental properties. One objective of this research is to search for s-factorisations of connected graphs and find short certificates to explain these cases. We searched all the stability polynomials of connected graphs of order at most 9 and found 17,461,965 s-factorisations corresponding to 273,192 graphs. These correspond to 152 different stability polynomials that have s-factorisation. We use \textit{certificates} to explain these s-factorisations. A \textit{certificate} is a sequence of expressions $S_{1},S_{2},\ldots, S_{k}$ satisfying the following properties. The first expression $S_{1}$ is the graph $G$. Each expression $S_{i}$ is obtained from $S_{i-1}$ by applying a property of the stability polynomial or an algebraic property. If the last expression is the graph $H$ then we have a \textit{certificate of equivalence}. If the last expression $S_{k}$ is the product of the graphs $H_{1}$ and $H_{2}$ then we have a \textit{certificate of factorisation}. A \textit{certificate step} is a rule that uses some properties of the graph polynomial or algebraic properties to transform one expression to another \cite{Morgan-2010}. A single certificate step is usually not enough to explain an s-factorisation. We found s-factorisable connected graphs have order $\geq 6$. Short certificates of s-factorisations for all stability polynomials of graphs of order at most 8 are given. Short certificates for two infinite families of s-factorisations were found. Another objective of this research is to find bounds for the lengths of certificates of s-factorisations and stability equivalence. We find upper bounds on the lengths of certificates of s-factorisations and stability equivalence, which are both exponential. The lengths of the short certificates we found for two infinite families are all constant values, which are significantly lower than the theoretical upper bounds. But we also give evidence that the lengths of certificates of equivalence cannot always be much shorter than quadratic. The length of certificates may have implications for the computational complexity of stability equivalence and factorisation, which we discuss. We also find certificate schemas for some certificates of s-factorisations. If there is a set of graphs that have s-factorisations which can be explained by certificates that use the same sequence of steps, these certificates will be generalised to a \textit{certificate schema}. We found two certificate schemas by analysing the patterns in short certificates of s-factorisations. This paper contains ten sections. Section 1 gives an overview of this research and introduces some definitions and notation. Section 2 introduces some properties of the stability polynomial, shows the relationship between the stability polynomial and some other graph polynomials and studies the previous research on graph polynomial factorisation. Section 3 presents computational results. Section 4 gives the certificate steps of the stability polynomial. Section 5 finds upper bounds for the length of certificates of stability equivalence. Section 6 examines the relationship between certificate length and computational complexity. It also gives a provisional lower bound on the lengths of some certificates of equivalence. Short certificates of stability equivalence and s-factorisations are presented in Section 7 and 8. Section 9 generalises some short certificates of s-factorisations and gives two certificate schemas. Section 10 summarises our work and and points to some directions of future research. \subsection{Definitions and notation} Graphs defined in this paper are listed in Table \ref{tab:Graphs defined in this thesis}. Some notation used in this paper is listed as follows. ${\overline{K}_{n}}$: the graph of order $n\geq 0$ with no edges; $C_{n}$: the cycle of order $n$; $K_{n}$: the complete graph of order $n$; $P_{n}$: path graph of order $n$ with $n-1$ edges; $ G - v $: a graph obtained from $G$ by deleting vertex $v$; $ G \cup G'$: disjoint union of graphs $G$ and $G'$; $ G + e $: a graph obtained from $G$ by adding the edge $e$; $ G + G' $: any graph obtained from $G$ and $G'$ by choosing one vertex from each graph and adding an edge between this pair of vertices. A \textit{null graph} is a graph with no edges. The \textit{independence number} $\alpha (G)$ is the size of a maximum stable set in graph $G$ \cite{Rosenfeld-2010}. \begin{table}[ht] \begin{center} %\begin{tabular}{| c r r r r |} \begin{tabular}{| c | l | l | } \hline \multicolumn{1}{|c}{ Notation} & \multicolumn{1}{|c|}{Explanation} & \multicolumn{1}{|c|}{Location in paper} \\ \hline \hline%heading $Q_{n}$ & The graph of order $n$ with & Thm \ref{thm:1}, Cor. \ref{cor:Qn=Yn+1}\\ & $ E(Q_{n})=\lbrace{v_{0}v_{2}}\rbrace \cup\lbrace{v_{i}v_{i+1}} : 0\leq i \leq n-2 \rbrace$, $n \geq 3$ & Cor. \ref{cor:Path2n}, Fig.{} \ref{fig:cycleYnThm}\\ \hline $Y_{n}$ & The graph of order $n$ with & Cor. \ref{cor:Qn=Yn+1}, Fig. \ref{fig:Qn=Yn+1} \\ & $ E(Y_{n})=\lbrace{v_{0}v_{2}}\rbrace \cup\lbrace{v_{i}v_{i+1}} : 1\leq i \leq n-3 \rbrace \cup\lbrace{v_{n-1}v_{1}} \rbrace$ &\\ &$\text{where } n \geq 4$ &\\ \hline $K^{*}_{n}$ & The graph of order $2n$ with & Cor. \ref{cor:KnStar}, Fig. \ref{fig:KnStar}\\ & $E(K^{*}_{n})=\lbrace{v_{i}v_{n+i}}: 0\leq i \leq n-1 \rbrace$ & \\ & $\cup\lbrace{v_{j}v_{k}} : 0\leq j,k \leq n-1, j\neq k \rbrace$, $n \geq 1$ & \\ \hline $\Upsilon_{m,n}$ & The graph of order $n$ with & Thm \ref{thm:Tn}, Fig. \ref{fig:Thm3Tn} \\ &$ E(\Upsilon_{m,n})=\lbrace{v_{i}v_{i+1}} : 0\leq i \leq n-2 \rbrace$ & \\ &$ \cup\lbrace{v_{m-1}v_{j}} : 0\leq j \leq m-3 \rbrace $ &\\ &$\text{where } 3\leq m\leq n$ &\\ \hline $K_{n \sim n}$& $K_{n \sim n} = K_{n} + K_{n}$ & Cor. \ref{cor:Knn}, Fig. \ref{fig:Knn} \\ \hline \end{tabular} \caption{Graphs defined in this paper}\label{tab:Graphs defined in this thesis} \end{center} \end{table} \section{Background} \subsection{Relationships between the stability polynomial and other graph polynomials}\label{section:RelationshipsOtherPolynomials} The stability polynomial is closely related to the independence polynomial, the chromatic polynomial and other polynomials. \bigskip %\subsubsection{The independence polynomial} \noindent {\bf The independence polynomial} \medskip \noindent The \textit{independence polynomial} $I(G;x)$ is a generating polynomial for the number of stable sets $s_{i}$ of cardinality $i$ \cite{Gutman-1983}. It can be expressed as \begin{align} \label{eqn:3.1} I(G;x) = \sum_{\text{X stable}}x^{|X|} = \sum_{i=0}^{\alpha (G)}s_{i}x^{i} \end{align} where $\alpha (G)$ is the size of a maximum stable set in $G$. $A(G; p)$ and $I(G; x)$ are related to each other by the following transformation. It is well known that \begin{align} \label{eqn:3.3} A(G;p) = (1-p)^{n}I\left(G;\frac{p}{1-p} \right) \end{align} and \begin{align} \label{eqn:3.4} I(G;x) = (1+x)^{-n}A\left(G;\frac{x}{1+x} \right) \end{align} When $|G|=|H_{1}|+|H_{2}|$, any results on s-factorisation $A(G;p)=A(H_{1};p)A(H_{2};p)$ can be translated to analogous factorisations for the independence polynomial, the clique polynomial and the positive matching polynomial. \bigskip \noindent {\bf The chromatic polynomial} \medskip \noindent The chromatic polynomial of a graph $G = (V, E)$ is \begin{align}\label{thm:old3.5} \CP{G} = \sum_{X\subseteq E} (-1)^{|X|}\lambda^{n-\rho(X)} \end{align} where $n$ is the number of vertices of $G$, and $\rho(X)$ is the rank of $X$. It follows from \eqref{thm:old3.5} that \begin{align} \label{eqn:3.5} \frac{\CP{G}}{\lambda^{n}}=\sum_{X\subseteq E} (-1)^{|X|}\lambda^{-\rho(X)} . \end{align} The stability polynomial can be written \cite{Helgason-1974} \begin{align} \label{eqn:3.6} A(G;p)= \sum_{X\subseteq E} (-1)^{|X|}p^{\nu(X)} \end{align} where $\nu(X)$ is the number of vertices that are incident with edges in $X$. We note that $\nu$ is the rank function of a $2$-polymatroid. When $p=\frac{1}{\lambda}$, (\ref{eqn:3.6}) becomes \begin{align} A\left(G;\frac{1}{\lambda}\right)= \sum_{X\subseteq E} (-1)^{|X|}\lambda^{-\nu(X)}.\label{eqn:3.6_1} \end{align} This was first shown in \cite{Helgason-1974}. When we compare \eqref{thm:old3.5} and \eqref{eqn:3.6_1}, we note that the right hand sides only differ in the rank function: $\rho$ is the rank of the cycle matroid of $G$ while $\nu(X)$ is the rank function of a 2-polymatroid. So the stability polynomial is a cousin of the chromatic polynomial: it plays the same role for graphic 2-polymatroid that the chromatic polynomial plays for matroids. This is what motivates us to investigate factorisation and equivalence for stability polynomials, having already done so for chromatic polynomials \cite{Morgan-2010, mf-2008-2, Morgan-2009} \subsection{Properties of the stability polynomial} \label{sec:Properties of the stability polynomial} In this section we give five interesting properties of the stability polynomial. They enable us to compute the stability polynomial of a graph recursively. They may be found, in different forms, in one or more of \cite{Farr-1991, Gutman-1983, Reicher-1997}. We will use these properties in our certificate steps in Section \ref{sec:Certificate steps}. \begin{thm}\label{thm:old5.1} (\cite{Gutman-1983}, in terms of I(G;x)) For any vertex $v \in V(G)$ which is not incident to a loop, there is \begin{align} \label{eqn:old5.1} A(G; p) = (1 - p)A(G - v; p) + p(1 - p)^{d}A(G - v - N(v); p) \end{align} where $d$ is the degree of vertex $v$ and $N(v)$ is the neighbour set of $v$. \end{thm} \begin{thm}\label{thm:old5.2} \cite{Reicher-1997} For any edge $uv \in E(G)$, \begin{align*} A(G; p) = (1-p)A(G-u; p) + (1 - p)A(G - v; p) - (1 - p)^{2} A(G-u-v; p). \end{align*} \end{thm} \begin{propn}\label{thm:old5.3} \cite{Gutman-1983} Let $H_{1}$ and $H_{2}$ be two disjoint graphs. If $G = H_{1} \cup H_{2}$, then \begin{align} \label{eqn:old5.3} A(G; p) = A(H_{1} ; p) A(H_{2} ; p). \end{align} \end{propn} \begin{propn}\label{thm:old5.4} Let $G$ be a graph with loops, $L$ is the set of vertices incident to loops. Then \begin{align*} A(G; p) = (1-p)^{|L|}A(G-L; p). \end{align*} \end{propn} \begin{thm}\label{thm:old5.5} \cite{Farr-1991} For any edge $uv \in E(G)$, \begin{align*} A(G; p) = A(G \backslash uv; p)-p^2(1-p)^{d_{uv}} A(G-u-v-N(u)-N(v); p) \end{align*} where $d_{uv} = |(N(u)\backslash \{v\}) \cup (N(v)\backslash \{u\})|$. \end{thm} Proposition \ref{thm:old5.3} is a basic case of stability polynomial factorisation. It gives a case of factorisation when the graphs $H_{1}$ and $H_{2}$ are disjoint. In this project we will find s-factorisations of graphs that do not have disjoint components but still satisfy (\ref{eqn:old5.3}). Studying s-factorisations may result in new rules for stability polynomials. A new rule is a proposition which can be explained by a certificate schema. \subsection{Graph polynomial factorisation} We review research on factorisation of chromatic polynomials and consider the relationship to the work of this paper. \subsubsection{Chromatic factorisations} \label{sec:Research on chromatic factorisations} The chromatic polynomial $\CP{G}$ is said to have \textit{chromatic factorisation} \cite{Morgan-2010} with \textit{chromatic factors} $H_{1}$ and $H_{2}$ if \begin{align} \label{eqn:5.1} \CP{G} = \frac{\CP{H_{1}}\CP{H_{2}}}{\CP{K_{r}}} \end{align} where $H_{1}$ and $H_{2}$ are not isomorphic to $K_{r}$ and have $\chi(H_{i}) \geq r, i=1,2$. A graph G has a chromatic factorisation if $\CP{G}$ does. Any \textit{clique-separable} graph, that is, a graph that can be obtained by identifying $r$-clique in $H_{1}$ with an $r$-clique in $H_{2}$, has a chromatic factorisation. It follows that any graph that is \textit{chromatically equivalent} to (i.e., has the same chromatic polynomial as) a clique-separable graph also has a chromatic factorisation. Morgan and Farr \cite{Morgan-2009, mf-2008-2} defined a graph to be \textit{strong non-clique-separable} if it is not chromatically equivalent to any clique-separable graph. Perhaps surprisingly, they found graphs that are strongly non-clique-separable, yet have a chromatic factorisation, identifying all such cases with at most 9 vertices, as well as an infinite family. They introduced the concept of a \textit{certificate} in order to explain these chromatic factorisations \cite{Morgan-2009}. Certificates have also been used to explain chromatic equivalence \cite{m-2009-17}. A \textit{certificate of chromatic factorisation} is a sequence of expressions $P_{0}, P_{1},\ldots, P_{i}$ where $P_{0} =\CP{G}$ and $P_{i} =\CP{H_{1}}\CP{H_{2}}/\CP{K_{r}}$ such that each $P_{j}$, $1\leq j \leq i$, is obtained from $P_{j-1}$ by applying an algebraic property or a property of the chromatic polynomial. This certificate is used to explain why a given graph $G$ has a chromatic factorisation with chromatic factors $H_{1}$ and $H_{2}$. Similarly a \textit{certificate of chromatic equivalence} is a sequence of expressions $P_{0}$, $P_{1}$,$\ldots$, $P_{i}$ where $P_{0} =\CP{G}$ and $P_{i} =\CP{H}$ such that each $P_{j}$, $1\leq j \leq i$, is obtained from $P_{j-1}$ by applying an algebraic property or a property of the chromatic polynomial. This certificate is used to explain why graphs $G$ and $H$ have the same chromatic polynomial. Certificates may give a means of verifying these properties of chromatic polynomials without computing these polynomials from scratch (which is $\#$P-hard). They give explanations of chromatic factorisation and chromatic equivalence that are purely graph theoretic, making no explicit use of polynomial algebra. Certificates have been used to explain the chromatic factorisations of all strongly non-clique-separable graphs of order at most 9 \cite{Morgan-2009}, to explain chromatic factorisation of an infinite family of strongly non-clique-separable graphs \cite{mf-2008-2}, to show that every non-bipartite graph can be the chromatic factor of a chromatic factorisation $\CP{H_{1}}\CP{H_{2}}/\CP{K_{3}}$ \cite{mf-2009-3} and to find pairs of chromatically equivalent graphs \cite{m-2009-17}. Interestingly, although theoretically these certificates could be exponentially long \cite{Morgan-2009}, in practice they are remarkably short. The length of these certificates have implications for the computational complexity of testing for chromatic equivalence, and of testing for the existence of a chromatic factorisation. In each case, if certificate length is bounded by a polynomial in graph size, then the problem belongs to NP \cite{Bukovac-2013}. \subsubsection{Connections with current research}\label{sec:Feasibility of s-factorisation research} As certificates have proved to be a powerful tool in explaining algebraic properties such as factorisation and equivalence for the chromatic polynomial and we have seen that the stability polynomial is closely related to the the chromatic polynomial (see (\ref{eqn:3.5}) and (\ref{eqn:3.6})), we use certificates to explain algebraic properties of the stability polynomial, namely $s$-factorisation and stability equivalence. While the certificates used for the chromatic polynomial used certificate steps based on properties of the chromatic polynomial, the certificates used in our research are based on properties of the stability polynomial. In Section \ref{sec:Certificate steps} we define a set of certificate steps based on the properties for the stability polynomial given in Section \ref{sec:Properties of the stability polynomial}. We then use these steps to give certificates of $s$-equivalence for some infinite families of graphs in Section \ref{sec:Stability equivalence} and certificates of $s$-factorisation for some infinite families of graphs in Section \ref{sec:S-factorisations}. Theorem \ref{thm:old5.1}, \ref{thm:old5.2} and \ref{thm:old5.5} in Section \ref{sec:Properties of the stability polynomial} can be used to construct recursive algorithms for the computation of the stability polynomial. We implemented an algorithm using (\ref{eqn:old5.1}) to calculate the stability polynomial. According to Farr \cite{Farr-2011}, the time complexity of this algorithm is $O(2^{n}\, \operatorname{poly}(n))$, which is more efficient than the usual recursive deletion-contraction algorithm for computing the chromatic polynomial. This means that the stability polynomial can be computed for graphs of larger order than the chromatic polynomial. \section{Computational results on s-factorisations} \label{sec:Computation results} By Proposition \ref{thm:old5.3}, any disconnected graph $G$ has an s-factorisation $A(G;p)$ $=$ $A(H_{1};p) \cdot A(H_{2};p)$ where $H_{1}$ and $H_{2}$ are two disjoint components of G. However, it was not known if any connected graph has an $s$-factorisation. In this paper we focus on s-factorisations of connected graphs. We calculated the stability polynomials of all connected non-isomorphic graphs of order at most 9 using a recursive algorithm based on (\ref{eqn:old5.1}). The base case of this recursive algorithm is $A({\overline{K}_{n}};p)=1$. If $G$ has edges, then we compute $A(G;p)$ as the sum of two recursive calculations, $A(G-v;p)$ and $A(G-v-N(v);p)$. We then exhaustively searched for $s$-factorisations. The computational results show that there are 17,461,965 s-factorisations corresponding to 28,576 s-factorisable graphs. These s-factorisable graphs have 152 different stability polynomials. Detailed results are given in Table \ref{tab:Graphs and the stability polynomials} and Table \ref{tab:s-factorisations}. \begin{table}[h] \begin{center} %\begin{tabular}{| c r r r r |} %\begin{tabular}{| c r r r r |} \begin{tabular}{| c | r | r | r | r |} \hline \multicolumn{1}{|c|}{ Order} & \multicolumn{1}{c|}{$\#$Graphs} & \multicolumn{1}{c|}{$\#$Different polys} & \multicolumn{1}{c|}{$\#$s-factorisable} & \multicolumn{1}{c|}{$\#$Different}\\ %heading \multicolumn{1}{|c|}{ } & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{graphs} & \multicolumn{1}{c|}{s-factorised polys}\\ \hline \hline %heading 2 &1& 1 &0 &0\\ 3 &2& 2 &0 &0\\ 4 &6& 5 &0 &0\\ 5 &21& 13 &0 &0\\ 6 &112& 38 &4 &3\\ 7 &853& 116 &50 &9\\ 8 &11117& 391 &955 &42\\ 9 &261080& 1438 &27567 &143\\ \hline \end{tabular} \caption{Graphs and the stability polynomials}\label{tab:Graphs and the stability polynomials} \end{center} \end{table} \begin{table}[ht] \begin{center} %\begin{tabular}{| c c c c c c c |} %\begin{tabular}{| c r r r r r r |} \begin{tabular}{| c | r | r | r | r |r | r |} \hline \multicolumn{1}{|c|}{Order} & \multicolumn{1}{c|}{A} & \multicolumn{1}{c|}{B} & \multicolumn{1}{c|}{C}&\multicolumn{1}{c|}{D} &\multicolumn{1}{c|}{E}& \multicolumn{1}{c|}{F} \\ \hline \hline 2 &1 & 1 &0 &0 & 0 &0\\ 2-3 &3 &3 &0 &0 &0 &0\\ 2-4 &9 &7 &0 &0 &0 &0\\ 2-5 &30 &17 &0 &0 &0 &0\\ 2-6 &142 &45 &4 &3 &18 &3\\ 2-7 &995 &130 &54 &10 & 741 & 10\\ 2-8 &12112 &420 &1009 &44 & 73617 & 44\\ 2-9 &273192 &1503 &28576 &152 & 17461965 &152\\ %note: s-factorisation graphs and different s-polys column should be updated when result of order 2-9 is ready, the first table should be counting in a more reasonable way] \hline \end{tabular}\\ \caption{s-factorisations}\label{tab:s-factorisations} (A) Number of non-isomorphic graphs, (B) Number of different stability polynomials, (C) Number of s-factorisable graphs, (D) Number of different s-factorisable stability polynomials, (E) Number of s-factorisations, (F) Number of different s-factorisations. \end{center} \end{table} For each order, Table \ref{tab:Graphs and the stability polynomials} gives the number of non-isomorphic graphs, the number of different stability polynomials, the number of graphs that have s-factorisation and the number of different stability polynomials that can be s-factorised. Table \ref{tab:s-factorisations} gives the accumulated data about s-factorisations of graphs, including the number of connected graphs that can be s-factorised (Column C), the number of different stability polynomials that can be s-factorised (Column D) and the number of different s-factorisations (Column F). Table \ref{tab:Graphs and the stability polynomials} shows that connected graphs which have s-factorisations have order $\geq 6$. By analysing the ratio between the number of graphs of order $n$ and the number of different stability polynomials of these graphs, we can see that when the order of graphs increases, the probability that different graphs have the same stability polynomials gets higher as $n$ increase. Table \ref{tab:s-factorisations} shows that 28,576 of the 273,192 connected graphs of order 2 to 9 can be s-factorised. These s-factorisable graphs correspond to 152 different stability polynomials, and have 152 different s-factorisations. Another interesting fact given by Table \ref{tab:s-factorisations} is that the values in Column D are the same as the values in Column F, which means the number of different s-factorisable stability polynomials is equal to the number of different s-factorisations. This finding may suggest that a stability polynomial can be s-factorised in at most one way. Our computational results confirmed that there are many cases of s-factorisation. A closer examination of the graph data summarised here also gave insights into possible families of graphs that have s-factorisations. By analysing the structure of these graphs, we identified several infinite families of graphs that have s-factorisations and found certificates of s-factorisation to explain the factorisations. \section{Certificate steps}\label{sec:Certificate steps} Just as for the chromatic polynomial, we introduce certificates for the stability polynomial in order to give graph theoretic explanations of properties of these polynomials. In this section we give certificate steps based on the properties of the stability polynomial which are presented in Section \ref{sec:Properties of the stability polynomial}. We then define certificates of s-factorisation and certificates of $s$-equivalence. \begin{description} \item \textbf{CS1 } $A({\overline{K}_{n}}; p)$ becomes 1. \item \textbf{CS2 } 1 becomes $A({\overline{K}_{n}}; p)$. \end{description} Figure \ref{fig:CS1and2} illustrates CS1 and CS2. In this paper, we use the convention of representing the stability polynomial of a graph by a picture of the graph itself. \begin{figure}[ht!] \begin{center} \includegraphics[width=4cm]{CS1and2.eps} \\ \caption{$A({\overline{K}_{n}}; p) \leftrightarrow 1, \text{ } n=3$} \label{fig:CS1and2} \end{center} \end{figure} \begin{description} \item \textbf{CS3 } $A(G; p)$ becomes $(1-p)A(G-v; p)+p(1-p)^{ d}A(G-v-N(v); p)$ for some vertex $v\in V(G)$ where $ d$ is the degree of vertex $ v $. (Theorem \ref{thm:old5.1}) \item \textbf{CS4 } Let $U=\lbrace{u_{1},u_{2}, u_{3},\ldots,u_{d}}\rbrace$ be $ d $ distinct vertices in $V(G_{1})$. Then $(1-p)A(G_{1}; p)+p(1-p)^{d}A(G_{2}; p)$ becomes $A(G; p)$ where $G=(V,E)$ is isomorphic to the graph $G'$ with vertex set $V' = V(G_{1})\cup\lbrace{v}\rbrace$, and edge set $E'=E(G_{1})\cup\lbrace{vu_{i}: \text{where } u_{i} \in U}\rbrace $, and where $G_{2} \cong G_{1} - U - \lbrace{v}\rbrace $. \text{(Theorem \ref{thm:old5.1})} \end{description} Figure \ref{fig:CS3and4} illustrates CS3 and CS4. \begin{figure}[h!] \begin{center} \includegraphics[width=10cm]{CS3and4.eps} \caption{$A(G; p) \leftrightarrow (1-p)A(G-v; p)+p(1-p)^{ d}A(G-v-N(v); p)$} \label{fig:CS3and4} \end{center} \end{figure} \begin{description} \item \textbf{CS5 } $A(G; p)$ becomes $(1-p)A(G-u; p)+(1-p)A(G-v;p)-(1-p)^{2}A(G-u-v;p)$ for some $uv\in{E(G)}$. (Theorem \ref{thm:old5.2}) \item \textbf{CS6 } Let $N_{1}\subseteq V(G_{3})$ and $N_{2}\subseteq V(G_{3})$. Then $(1-p)A(G_{1}; p)+(1-p)A(G_{2};p)-(1-p)^{2}A(G_{3};p)$ becomes $A(G; p)$ for some $uv\in{E(G)}$ where the following conditions are satisfied: \begin{description} \item (1) $G_{1}(V_{1},E_{1})$ is isomorphic to the graph with $V'_{1} =V(G_{3})\cup\lbrace{u}\rbrace $ and $E'_{1}=E(G_{3})\cup\lbrace{ua:a \in N_{1}}\rbrace$, \item (2) $G_{2}(V_{2},E_{2})$ is isomorphic to the graph with $V'_{2} =V(G_{3})\cup\lbrace{v}\rbrace $ and $E'_{2}=E(G_{3})\cup\lbrace{vb:b \in N_{2}}\rbrace$, \item (3) $G(V,E)$ is isomorphic to the graph with $V' =V(G_{3})\cup\lbrace{u}\rbrace\cup\lbrace{v}\rbrace $ and $E'=E(G_{3})\cup\lbrace{ua:a \in N_{1}}\rbrace\cup\lbrace{vb:b \in N_{2}}\rbrace$. \end{description} (Theorem \ref{thm:old5.2}) \end{description} Figure \ref{fig:CS5and6} illustrates CS5 and CS6. \begin{figure}[ht!] \begin{center} \includegraphics[width=13cm]{CS5and6.eps} \caption{$A(G; p) \leftrightarrow (1-p)A(G-u; p)+(1-p)A(G-v;p)-(1-p)^{2}A(G-u-v;p)$} \label{fig:CS5and6} \end{center} \end{figure} \begin{description} \item \textbf{CS7 } $A(G;p)$ becomes $A(G\setminus{e}; p)-p^{2}(1-p)^{d}A(G-u-v-N(u)-N(v); p)$ for some $uv\in{E(G)}$ and $d=\vert(N(u)\setminus\lbrace{v}\rbrace)\cup{(N(v)\setminus\lbrace{u}\rbrace)}\vert.$ (Theorem \ref{thm:old5.5}) \item \textbf{CS8 } $A(G_{1}; p) - p^{2}(1-p)^{d}A(G_{2}; p)$ becomes $ A(G; p)$ where\\ $G(V, E)$ is isomorphic to the graph with $V=V(G_{2})\cup\lbrace{u}\rbrace\cup\lbrace{v}\rbrace$ and $E=E(G_{2})\cup\lbrace{ua:a\in{N_{1}}}\rbrace\cup\lbrace{vb:b\in{N_{2}}}\rbrace$ when $N_{1}\subseteq{V(G_{2})}, N_{2}\subseteq{V(G_{2})}$ and $d=\vert{N_{1}\cup{N_{2}}}\vert.$ (Theorem \ref{thm:old5.5}) \end{description} Figure \ref{fig:CS7and8} illustrates CS7 and CS8. \begin{figure}[h!] \begin{center} \includegraphics[width=11cm]{CS7and8.eps} \caption{$A(G; p) \leftrightarrow A(G\setminus{e}; p)-p^{2}(1-p)^{d}A(G-u-v-N(u)-N(v); p)$} \label{fig:CS7and8} \end{center} \end{figure} \begin{description} \item \textbf{CS9 } $A(G;p)$ becomes $A(G_{1}; p)A(G_{2}; p)$ where $G_{1},G_{2}$ are two disjoint graphs and $G_{1}\cup{G_{2}}$ is isomorphic to $G$. (Proposition \ref{thm:old5.3}) \item \textbf{CS10 } $A(G_{1}; p) A(G_{2}; p)$ becomes $A(G;p)$ where $G_{1},G_{2}$ are two disjoint graphs and $G$ is isomorphic to $G_{1}\cup{G_{2}}$. (Proposition \ref{thm:old5.3}) \end{description} Figure \ref{fig:CS9and10} illustrates CS9 and CS10. \begin{figure}[h!] \begin{center} \includegraphics[width=7cm]{CS9and10.eps} \caption{$A(G; p) \leftrightarrow A(G_{1}; p) A(G_{2}; p)$} \label{fig:CS9and10} \end{center} \end{figure} \begin{description} \item \textbf{CS11 } Algebraic step. \end{description} There is some room for variety in the choice of our certificate steps. Some of the given steps could be dropped, since they could be proved (at some cost, in terms of extra steps) using others. The steps we have chosen correspond to the simplest recurrence relations that can be given for the stability polynomial. These certificate steps can be used to explain s-factorisations and stability equivalences. A \textit{certificate} is a sequence of expressions $P_{0}, P_{1},\ldots, P_{i}$, such that, for every $j, 1 \leq j \leq i,$ $P_{j}$ in the sequence is obtained from $P_{j-1}$ by applying one of the certificate steps of stability polynomials. A \textit{certificate of stability equivalence} for graph $G$ and $H$ has $P_{0} = A(G;p)$ and $P_{i} = A(H;p)$. A \textit{certificate of stability factorisation} has $P_{0} = A(G;p)$ and $P_{i} = A(G_{1}; p) A(G_{2}; p)$. The certificate steps which are obtained from the properties of the stability polynomial are given in $\mathrm{CS1},\ldots, \mathrm{CS11}$. We consider how the length of the certificates depends on the order of the corresponding graphs. \section{Upper bound for certificate length} \label{sec:Upper bound of certificate length} In this section we will discuss the lengths of certificates for stability equivalences and s-factorisations. We use a naive approach to find an upper bound on length of certificates. In practice we found much shorter certificates. To show two graphs are stability equivalent we must transform expression $A(G; p)$ to expression $A(H; p)$ using certificate steps. We do this in two phases. First we transform the stability polynomial of $G$ to an expression in null graphs. Then we transform this expression into the stability polynomial of $H$. To show $A(G;p)$ has factorisation $A(H_{1}; p)A(H_{2};p)$ we must transform expression $A(G; p)$ to expression $A(H_{1}; p)A(H_{2};p)$. We can also first transform the stability polynomial of $G$ into expression in null graphs and then transform this expression into product of the stability polynomial of $H_{1}$ and the stability polynomial of $H_{2}$. First of all, we use a naive approach to express the stability polynomial of graph $G$ in terms of null graphs and find an upper bound for the number of certificate steps required to do so. For any graph $G$, if there exists a vertex $v \in V(G)$ with degree $\geq 1$, we apply certificate step CS3 on $v$ and transform $A(G;p)$ to $(1-p)A(G-v; p)+p(1-p)^{deg \text{ } v}A(G-v-N(v); p)$. If graphs $G-v$ and $G-v-N(v)$ are not null graphs, we recursively apply CS3 on these graphs until all graphs in the expression are null graphs. Let $t_n$ be the maximum number of certificate steps required to express the stability polynomial of any graph on $n$ vertices in terms of null graphs. This is the same as the number of applications of Theorem 1 required to compute the polynomial recursively. Observe that $t_1=0$ and $t_2=1$. To get a simple upper bound for $t_n$, observe that a single application of CS3 produces a graph of $n-1$ vertices, which requires $t_{n-1}$ further steps, and a graph of $n-1-\deg v\le n-2$ vertices (where $v$ is the vertex at which CS3 is used on $G$, which we choose so that $\deg v\ge1$), which requires $\le t_{n-2}$ further steps (unless $G$ is a null graph, but in that case we are done already). So $t_n \le 1 + t_{n-1} + t_{n-2}$. Putting $s_n:=t_n+1$, we have $s_n\le s_{n-1} + s_{n-2}$. Hence $s_n$ is bounded above by a Fibonacci sequence. It follows that $t_n=O(\varphi^n)$, where $\varphi=(1+\sqrt{5})/2\simeq1.618$ is the golden ratio. A little more care gives a stronger upper bound. \begin{lemma}\label{lem:positiveRoot} %\[ %t_n=O(\psi^n), %\] \,\, $t_n=O(\psi^n)$ where $\psi\simeq1.380$ is the positive root of $x^4-x^3-1=0$. \end{lemma} \begin{proof} (sketch) We suppose that, throughout the computation, we always use CS9 whenever we have a disconnected graph, and CS3 whenever the graph is connected. If we encounter a graph of maximum degree $\le2$, then it is easily dealt with. It is routine to show that the computation for such a graph requires only a linear number of certificate steps. If the maximum degree is $\ge3$, we choose a vertex $v$ of degree $\ge3$ and apply CS3 there. This gives $t_n\le1+t_{n-1}+t_{n-4}$. With $s_n=t_n+1$ as before, we have $s_n\le s_{n-1}+s_{n-4}$. Using standard theory of recurrence relations, we obtain $s_n=O(\psi^n)$, where $\psi$ is the positive root of the characteristic equation of the recurrence, $x^4-x^3-1=0$. \end{proof} The first few values of $t_n$ are given in Table \ref{tab:certificate length}. We use $t_n$ to give an upper bound on the lengths of certificates of stability equivalence. \begin{thm} The maximum length $e_n$ of a certificate of stability equivalence for graphs of order $\leq n$ satisfies $e_n\le2t_n + 2n - 1$ and $e_n=O(\psi^n)$. \end{thm} \begin{proof} Suppose $A(G;p)=A(H;p)$, we can transform $G$ to a sum of null graphs in $\leq t_n$ applications of CS3, then use $ \leq n-1$ applications of CS1 to transform to $E_{G}(p)$, a polynomial in $p$. By applying an algebraic step CS11, $E_{G}(p)$ can be transform to a polynomial $E_{H}(p)$ in $p$, which can be transformed back to $H$ within $ t_n + n-1$ steps. Total certificate length is $\leq 2t_n + 2n -1 $. From Lemma \ref{lem:positiveRoot} it follows that $e_n=O(\psi^n)$. \end{proof} \begin{thm} Let $n, n_{1}, n_{2}$ be the orders of graph $G, H_{1}, H_{2}$, respectively. The maximum length $f_N$ of a certificate of s-factorisation $A(G;p)=A(H_1;p)A(H_2;p)$ satisfies $f_N \leq 3t_N + 3N -2$ where $N = max\{n, n_{1}, n_{2} \}$ and $f_N=O(\psi^N)$. \end{thm} \begin{proof} Similarly to the previous proof, we can transform $G$ to null graphs, use $ \leq n -1 $ applications of CS3, do algebra (this time, the algebra will produce an expression which is a product of two distinct parts), then transform one part of the resulting expression to $H_1$ and the other to $H_2$. This latter transformation is the reverse of the steps needed to compute each of $A(H_1;p)$ and $A(H_2;p)$. Putting it all together, we have $f_N \leq t_{n} + n -1 + 1 + t_{n_{1}}+ n_{1} - 1 + t_{n_{2}} + n_{2} - 1 \leq 3t_N + 3N -2$. The result follows. \end{proof} We use $N$ here, rather than any one of $n, n_{1}, n_{2}$, because in principle the factors $H_{i}$ may have more vertices than $G$ (even though their stability polynomials have lower degrees than that of $G$). From (\ref{eqn:3.6}) we can get $m = m_{1} + m_{2}$, where $m, m_{1}, m_{2}$ is the number of edges of graph $G, H_{1}, H_{2}$, respectively. Thus $m -1 \geq m_{i} \geq n_{i} -1$. So $ N \leq \binom{n}{2}$. We give the values of our upper bounds for $n\le9$ (since this is the range covered by our computations) in Table \ref{tab:certificate length}. The values of $t_n$ for $n\le4$ are exact. We also give exact values of $e_n$ and $f_N$ where we have determined them. The first three values of $e_n$ are zero because there are no non-isomorphic stability-equivalent graphs for $n\le3$. The entry $e_4=2$ comes from a certificate we give later, for $A(C_4;p)=A(Q_4;p)$ (Theorem 7). The first five values of $f_N$ are zero because there are no s-factorisations for $N\le5$.\\ \begin{table}[ht] \begin{center} \begin{tabular}{|r|rrrrrrrrr|} \hline $n = $ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \hline $t_n \le$ & 0 & 1 & 1 & 2 & 3 & 5 & 7 & 10 & 14 \\ $e_n =$ & 0 & 0 & 0 & 2 & & & & & \\ $e_n \le$ & & & & 11 & 15 & 21 & 27 & 35 & 45 \\ $f_N =$ & 0 & 0 & 0 & 0 & 0 & & & & \\ $f_N \le$ & & & & & & 31 & 40 & 52 & 67 \\ \hline \end{tabular} \caption{Maximum certificate length for graphs of order $n$}\label{tab:certificate length} \end{center} \end{table} \section{Certificate length and complexity} The problem of computing the stability polynomial of a graph is \#P-hard, since counting independent sets in a graph is \#P-complete. Consider now the following problems. ~\\ \noindent STABILITY EQUIVALENCE \\ \textsc{Input:} Graphs $G$ and $H$. \\ \textsc{Question:} Is $A(G;p)=A(H;p)$? \\ \noindent STABILITY FACTORISATION \\ \textsc{Input:} Graph $G$. \\ \textsc{Question:} Do there exist graphs $H_1$ and $H_2$, neither of which is a null graph or isomorphic to $G$, such that $A(G;p)=A(H_1;p)A(H_2;p)$? \\ STABILITY EQUIVALENCE can be solved with the aid of an oracle for \#P, since the oracle can be used to compute $A(G;p)$ and $A(H;p)$ and then compare them. Hence STABILITY EQUIVALENCE belongs to $\hbox{P}^{\hbox{\scriptsize\#P}}$, which is the class of decision problems solvable in polynomial time with the aid of a \#P oracle. For STABILITY FACTORISATION, a \#P-oracle yields $A(G;p)$. On the face of it, we are then stuck unless we know $H_1$ and $H_2$. If these are given to us, then we can use the \#P-oracle to compute $A(H_1;p)$ and $A(H_2;p)$ and hence verify that $A(G;p)=A(H_1;p)A(H_2;p)$. So STABILITY FACTORISATION belongs to $\hbox{NP}^{\hbox{\scriptsize\#P}}$, the class of decision problems which can be solved nondeterministically in polynomial time with the aid of a \#P-oracle. The notion of certificates of s-equivalence and s-factorisation opens up a new line of enquiry into the complexity of these problems. In principle, certificates allow us to verify s-equivalence, or a claimed s-factorisation, without computing the stability polynomials themselves. Verification only requires the verification of each certificate step, which can be done in polynomial time for each step. However, if the certificates are very long, then the amount of effort involved in verifying a certificate may be comparable with the effort required to compute the stability polynomials from scratch. We saw this in the previous section, when the certificates we used for our upper bounds on certificate length mimicked the computations of the polynomials. Nonetheless, it may be that our upper bounds are unnecessarily loose, and that much shorter certificates can be found. This may have implications for the complexity of our two problems. \begin{thm} (a) If the length of the shortest certificate of equivalence between two stability equivalent graphs of at most $n$ vertices is bounded by a polynomial in $n$, then STABILITY EQUIVALENCE is in NP. \\ (b) If the length of the shortest certificate of factorisation for a stability factorisation of a graph of $n$ vertices is bounded by a polynomial in $n$, then STABILITY FACTORISATION is in NP. \end{thm} \begin{proof} In each case, if certificate length is polynomially bounded, then the entire certificate can be verified in polynomial time (using the above observation that each step can be verified in polynomial time). \end{proof} It is encouraging that the certificates we have found empirically (see later sections) are short, although short certificates will tend to be easier to find! However, it seems unlikely that the shortest certificates of stability equivalence are $o(n^2/(\log n)^2)$, in general. This is because of the following result, whose proof is based on a suggestion of Ian Wanless. \begin{thm}\label{Thm:lengthOfSElowerBound} If the number of different stability polynomials of graphs of order $n$ is $\le2^{bn^2}$, for some constant $b<1/2$ and for sufficiently large $n$, then there exist pairs of stability equivalent graphs on $n$ vertices whose shortest certificate of stability equivalence has length $\Omega(n^2/(\log n)^2)$. \end{thm} \begin{proof} Suppose the number of different stability polynomials is $\le2^{bn^2}$, for sufficiently large $n$. Suppose $0 < \varepsilon < \frac{1}{2} - b $. The number of graphs on $n$ vertices, up to isomorphism, is at least $2^{(\frac{1}{2}- \varepsilon) n^2}$, for sufficiently large $n$ (see, e.g., \cite{Harary-1973}). From now on, suppose $n$ is large enough for this to hold. So there must exist a set of $\ge2^{(\frac{1}{2}- \varepsilon -b)n^2}$ stability equivalent graphs on $n$ vertices. Let $G$ be any one of these graphs. If every certificate of stability equivalence for graphs of order $n$ has length $\le L$, then the size of the stability equivalence class of $G$ is bounded above by the number of valid sequences of $L$ certificate steps starting with $G$. Now, if a certificate starts with a single graph and has length $\le L$, then each of its $L$ expressions (after $G$) can contain at most $L$ graphs. This is because each certificate step can increase the number of graphs by at most 1. Consider the number of possible applications of a certificate step to an expression of at most $L$ graphs. Firstly, there is the choice of the graph at which the step is applied (from $\le L$ possibilities), then possibly the choice of a vertex or two within the graph (from $\le n^2$ possibilities), then possibly the choice of the second graph needed for certain certificate steps (from $\le L-1$ possibilities), and even a third graph for some steps ($\le L-2$ possibilities). So there are $\le c_0 n^2 L^3$ choices altogether, for some constant $c_0$. The number of possible certificates of stability equivalence, starting with $G$ and of length $\le L$, is therefore $\le (c_0 n^2 L^3)^L = 2^{c_1 \cdot \log n \cdot \log L \cdot L}$ (with $c_1 = 6 \log_2 c_0$). This must be at least as great as the number of graphs in the stability equivalence class of $G$. Therefore \[ 2^{(\frac{1}{2}- \varepsilon -b)n^2} \le 2^{c_1 \cdot \log n \cdot \log L \cdot L}. \] Hence \begin{equation} \label{eq:ineq-for-LlogL} L \log L \ge c_2 \cdot \frac{n^2}{\log n} , \end{equation} where $c_2=(\frac{1}{2}- \varepsilon -b)/c_1$. Suppose $L\le c_3 n^2/((\log n)^2 f(n))$, for sufficiently large $n$, constant $c_3$ and appropriate choice of function $f$. Then (\ref{eq:ineq-for-LlogL}) gives \[ \frac{n^2}{(\log n)^2 f(n)} \cdot (2\log n - 2\log\log n - \log f(n) + \log c_3) \ge c_2 \cdot \frac{n^2}{\log n} , \] from which we conclude that $f(n)$ is bounded above by a suitable constant. (Here we use $c_{2} > 0$, which requires $b < \frac{1}{2}$.) It follows that any upper bound on certificate length must be $\Omega(n^2/(\log n)^2)$. \end{proof} The hypothesis of Theorem \ref{Thm:lengthOfSElowerBound} seems likely to be true. The data in Table \ref{tab:Graphs and the stability polynomials} suggests that $b < 0.15 $ and decreases as $n$ increases beyond $5$. \section{Stability equivalence}\label{sec:Stability equivalence} The computational results given in Section \ref{sec:Computation results} show that many non-isomorphic graphs have the same stability polynomial. In this section, short certificates for two infinite families of stability equivalent graphs are presented. \begin{thm}\label{thm:1} The stability polynomial $A(C_{n}; p)=A(Q_{n}; p)$ for $n \geq 3$. \end{thm} \begin{proof} The following is a certificate of equivalence to show $A(C_{n}; p)=A(Q_{n}; p)$: \begin{align*} A(C_{n}; p)&=(1-p)A(P_{n-1}; p)+p(1-p)^{2}A(P_{n-3}; p) &\text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS3)}\\ &=A(Q_{n}; p).&\text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS4)} \end{align*} This certificate is illustrated in Figure \ref{fig:cycleYnThm}. \end{proof} \begin{figure}[ht!] \begin{center} \includegraphics[width=13cm]{cycleYnThm.eps} \\ \caption{$A(C_{n}; p)=A(Q_{n}; p)$} \label{fig:cycleYnThm} \end{center} \end{figure} Theorem \ref{thm:1} shows that for any $n \geq 3 $, $A(C_{n}; p)=A(Q_{n}; p)$ has a certificate of length 2. The length of certificates for this infinite family of stability equivalences is much lower than the exponential upper bound given in Section \ref{sec:Upper bound of certificate length}. \begin{thm}\label{thm:2} For any $uv \in E(G)$, if $(N(v)\backslash\{{u}\})\subseteq(N(u)\backslash\{{v}\})$. Then \begin{align*} A(G; p)=A(G'; p) \end{align*} where $G'$ is a graph with $V(G') = V(G) \cup \{{w}\}, E(G')=(E(G)\backslash{uv})\cup\{{uw}\}$ \end{thm} \begin{proof} The following is a certificate of the stability equivalence: \begin{align*} A(G; p)=&(1-p)A(G-u; p)+p(1-p)^{\lvert{N(u)}\rvert}A(G-N(u); p) &\text{~~~~(CS3)}\\ =&(1-p)A(G-u; p)A(K_{1}; p)+p(1-p)^{\lvert{N(u)}\rvert}A(G-N(u); p)A(K_{1}; p) &\text{~~~~(CS2)}\\ =&(1-p)A(\{G-u\}\cup{K_{1}};p)\\ &+p(1-p)^{\lvert{(N(u)\backslash{\{v\}})\cup{\{w \}}}\rvert}A(\{G-N(u)\}\cup{K_{1}};p) &\text{~~~~(CS10)}\\ =&A(G'; p). &\text{~~~~(CS4)} \end{align*} Figure \ref{fig:Thm2Neighbour} illustrates this certificate. \end{proof} \begin{figure}[ht!] \begin{center} \includegraphics[width=13cm]{Thm2Neighbour.eps} \\ \caption{Edge breaking theorem} \label{fig:Thm2Neighbour} \end{center} \end{figure} Theorem \ref{thm:2} shows that an infinite family of graphs have stability equivalences that can be explained by certificates of length $4$. The length of certificates for these stability equivalences is much lower than the exponential upper bound given in Section \ref{sec:Upper bound of certificate length} and is independent of the order of the graph. Theorem \ref{thm:2} can be used to show the following two infinite families of graphs are stability equivalent. \begin{cor} \label{cor:Qn=Yn+1} For any $n \geq 3$, \begin{align*} A(Q_{n};p) =& A(Y_{n+1};p) &\square \end{align*} \end{cor} \begin{figure}[ht!] \begin{center} \includegraphics[width=13cm]{Corrallary2.1QnYn.eps} \\ \caption{$A(Q_{n};p) = A(Y_{n+1};p)$} \label{fig:Qn=Yn+1} \end{center} \end{figure} \begin{cor} \label{cor:KnStar} For any $n \geq 2$, \begin{align*} A(K_{n+1};p) = A(K^{*}_{n};p) \end{align*} \begin{proof} Let $\{v_{i}: 0 \leq i \leq n-1\} \cup \{w\}$ be the vertex set of $K_{n+1}$. Applying Theorem \ref{thm:2} on all edges in $\{ v_{i}w: 0 \leq i \leq n-1 \} $ will provide certificates for this infinite family of stability equivalences. Theorem \ref{thm:2} is used $n$ times. Thus the length of certificates provided by this proof is $4n$. This length is linear, which is much shorter than the exponential upper bound given in Section \ref{sec:Upper bound of certificate length}. This proof is illustrated in Figure \ref{fig:KnStar}. \end{proof} \end{cor} \begin{figure}[ht!] \begin{center} \includegraphics[width=10cm]{Corrallary2.2KnStar.eps} \\ \caption{$A(K_{n+1};p) = A(K^{*}_{n};p)$} \label{fig:KnStar} \end{center} \end{figure} \section{S-factorisations}\label{sec:S-factorisations} In this section, we studied the s-factorisations provided by the computational results and found short certificates for two infinite families of s-factorisations. \begin{thm}\label{thm:Tn}For any $n \geq 3$, we have \begin{align*} A(\Upsilon_{n,2n};p)=A(P_{n-1};p)A(\Upsilon_{n+1,n+1};p) \end{align*} \end{thm} \begin{proof}\label{proof:301} The following is a certificate of this s-factorisation: \begin{align*} A(\Upsilon_{n,2n}; p)&=(1-p)A(\Upsilon_{n,2n}\cup P_{n-1}; p)+p(1-p)^{2}A(P_{n-1}\cup{P_{n-2}}; p) &\text{~~~(CS3)}\\ &=(1-p)A(\Upsilon_{n,2n};p)A(P_{n-1}; p)+p(1-p)^{2}A(P_{n-1};p)A(P_{n-2}; p) &\text{~~~(CS9)$\times 2$}\\ &=A(P_{n-1}; p)[(1-p)A(\Upsilon_{n,n};p)+p(1-p)^{2}A(P_{n-2};p)] &\text{~~~(CS11)}\\ &=A(P_{n-1};p)A(\Upsilon_{n+1,n+1};p). &\text{~~~(CS4)} \end{align*} Figure \ref{fig:Thm3Tn} illustrates this certificate. The length of these certificates is 5, which is much lower than the exponential upper bound given in Section \ref{sec:Upper bound of certificate length}. \end{proof} \begin{figure}[ht!] \begin{center} \includegraphics[width=15cm]{Thm3Tn.eps} \\ \caption{$A(\Upsilon_{n,2n};p)=A(P_{n-1};p)A(\Upsilon_{n+1,n+1};p)$} \label{fig:Thm3Tn} \end{center} \end{figure} \begin{thm}\label{thm:GeneralSymmetry} (General symmetry theorem) Suppose $G \cong G' , u \in V(G)$, $u'$ is the image of $u$ in $G'$ under the isomorphism, $N(u)$ is the neighbour set of u in $G$. Let $N_{2}\subseteq{V(G_{2})}$, $G_{3}$ is a graph with vertex set $V(G_{3})=V(G)\cup{V(G')}\cup V(G_{2})$ and edge set $E(G_{3})=E(G)\cup{E(G')}\cup{E(G_{2})}\cup{\{uv,u'v:v\in N_{2}\}}\cup {\{uu'\}}$. Then \begin{align*} A(G_{3};p)=A(G-u;p)A(G_{4};p) \end{align*} where $G_{4}$ is a graph with vertex set $V(G_{4})=V(G_{2})\cup{V(G')}\cup{\{w\}}$ and edge set $E(G_{4})=E(G_{2})\cup{E(G')}\cup{\{wv,u'v:v\in{N(u)}\}}$ \end{thm} \begin{proof} The following is a certificate of this s-factorisation: \begin{align*} A(G_{3};p)=&p(1-p)^{\lvert{N(u)\cup{N_{2}}\cup{\{u'\}}}\rvert}A((G-u-N(u))\cup(G'-u') \cup(G_{2}-N_{2});p) \\ &+(1-p)A((G-u)\cup(G_{3}-G);p)\text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS3)}\\ =&p(1-p)^{\lvert{N(u)\cup{N_{2}}\cup{\{u'\}}}\rvert}A(G-u-N(u);p)A(G'-u';p)A(G_{2}-N_{2};p)\\ &+(1-p)A(G-u;p)A(G_{3}-G;p) \text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS9)$\times 2$}\\ =&p(1-p)^{\lvert{N(u)\cup{N_{2}}\cup{\{u'\}}}\rvert}A(G-u-N(u);p)A(G_{2}-N_{2};p)] \\ &+A(G-u;p)[(1-p)A(G_{3}-G;p)\text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS11)}\\ =&A(G-u;p)A(G_{4};p).\text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(CS6)}\\ \end{align*} The length of certificates provided by this proof is $5$. This independent of the order of the graph and is much lower than the exponential upper bound given in Section \ref{sec:Upper bound of certificate length}. Figure \ref{fig:Thm4GeneralSymmetry} illustrates this certificate. \end{proof} \begin{figure}[ht!] \includegraphics[width=15cm]{Thm4GeneralSymmetry.eps} \caption{General symmetry theorem} \label{fig:Thm4GeneralSymmetry} \end{figure} Theorem \ref{thm:GeneralSymmetry} is a property of stability polynomial which can be used to decompose certain graphs with isomorphic subgraphs. We applied Theorem \ref{thm:2} on some more specialised cases and found the following interesting corollaries. \begin{cor}\label{thm:3} (Symmetry corollary) If $G \cong G'$, $u \in V(G)$ and $u'$ is the image of $u$ in $G'$ under the isomorphism, $N(u)$ is the neighbour set of u in $G$. Let $G_{2}$ be a graph with vertex set $V(G_{2})=V(G)\cup{V(G')}$ and edge set $E(G_{2})=E(G)\cup{E(G')}\cup{\{uu'\}}$. Then \begin{align*} A(G_{2};p)=A(G-u;p)A(G_{u+};p) \end{align*} where $G_{u+}$ is a graph with vertex set $V(G_{u+})=V(G)\cup{\{w\}}$ and edge set $E(G_{u+})=E(G)\cup{\{wu\}}\cup{\{wv:v\in{N(u)}\}}$. \end{cor} Figure \ref{fig:Corrollary4.1Symmetry} illustrates this corollary. \begin{figure}[ht!] \begin{center} \includegraphics[width=10cm]{Corrollary4.1Symmetry.eps} \\ \caption{Symmetry corollary} \label{fig:Corrollary4.1Symmetry} \end{center} \end{figure} The length of certificates provided by Corollary \ref{thm:3} is $5$ steps. \begin{cor} \label{cor:existsSFactorisation} For any graph $G$, there exists a graph ${H}$ such that $H$ has an s-factorisation with $G$ as a factor. \end{cor} This result is analogous to one due to Morgan and Farr for chromatic factorisation \cite{Morgan-2009}. \begin{cor} \label{cor:Knn} For any $n \geq 2$, \begin{align*} A(K_{n \sim n };p)= A(K_{n-1};p)A(K_{n+1};p) \end{align*} \end{cor} Figure \ref{fig:Knn} illustrates this corollary. \begin{figure}[h!] \begin{center} \includegraphics[width=10cm]{Corrollary4.2Kn-1Kn+1.eps} \\ \caption{$A(K_{n \sim n };p)= A(K_{n-1};p)A(K_{n+1};p)$ when $n = 4$} \label{fig:Knn} \end{center} \end{figure} The length of certificates provided by Corollary \ref{cor:Knn} is $5$. \begin{cor}\label{cor:Path2n}For any $n \geq 2$, \begin{align*} A(P_{2n};p)=A(P_{n-1};p)A(C_{n+1};p). \end{align*} \end{cor} \begin{proof} Let $G$ be a $P_{n}$ and $G' \cong G , V(G)=\{{v_{0},v_{1},\ldots,v_{n}}\}, E(G)=\lbrace{v_{0}v_{2}}\rbrace \cup\lbrace{v_{i}v_{i+1}} : 0\leq i \leq n-2 \rbrace $ $G' \cong G$ and $v'_{i}$ is the image of $v_{i}$ in $G$ under the isomorphism. $G_{2} = (G \cup G')+{\{v_{0}v'_{0}\}}$, $G_{2}$ is a $P_{2n}$. $G_{4}$ is a $Q_{n}$ with vertex set $V(G_{4})={V(G')}\cup{\{w\}}$ and edge set $E(G_{4})={E(G')}\cup{\{wv,u'v:v\in{N_{G}(v'_{0})}\}}$. By Theorem \ref{thm:GeneralSymmetry}, $A(G_{2};p)=A(G-{v_{0}};p)A(G_{4};p)$. Thus \begin{align}\label{eqn:old4.1} A(P_{2n};p)=A(P_{n-1};p)A(Q_{n+1};p) \end{align} By Corollary \ref{cor:Qn=Yn+1} and Theorem \ref{thm:1} $A(Q_{n+1};p) = A(Y_{n+2};p) = A(C_{n+1};p)$. Applying this to (\ref{eqn:old4.1}) gives \begin{align*} A(P_{2n};p)=A(P_{n-1};p)A(C_{n+1};p). \end{align*} \end{proof} The length of these certificates is $5+2=7$. Figure \ref{fig:Path2n} illustrates this corollary. \begin{figure}[ht!] \begin{center} \includegraphics[width=13cm]{Corrollary4.3P2n=Pn-1Cn+1.eps} \\ \caption{$A(P_{2n};p)=A(P_{n-1};p)A(C_{n+1};p)$} \label{fig:Path2n} \end{center} \end{figure} \section{Certificate schemas of s-factorisations}\label{sec:Certificate schemas of s-factorisations} The certificates for s-factorisations presented in Section \ref{sec:S-factorisations} show that two different families of s-factorisations can be explained by the same sequence of certificate steps. We group these certificates of s-factorisations into two certificate schemas as follows: \begin{center} \fbox{ \addtolength{\linewidth}{-2\fboxsep}% \addtolength{\linewidth}{-2\fboxrule}% \begin{minipage}{14cm} \begin{align*} A(G;p) =&(1-p)A(H_{1};p) + p(1-p)^{d}A(H_{2};p) &\text{~~~~(CS3)} \\ =&(1-p)A(H_{3};p)A(H_{4};p) + p(1-p)^{d}A(H_{3};p)A(H_{5};p) &\text{ ~~~~(CS9)$\times$2} \\ =&A(H_{3};p) ((1-p)A(H_{4};p) + p(1-p)^{d}A(H_{5};p)) &\text{~~(CS11)} \\ =&A(H_{3};p)A(H_{6};p) &\text{~~~(CS4)} \end{align*} \begin{center} \textbf{Schema 1} \end{center} \end{minipage} } \end{center} The length of certificates constructed by Schema 1 is 5 steps. This schema can be used to build the certificates in Theorems \ref{thm:Tn} and \ref{thm:GeneralSymmetry} and Corollaries \ref{thm:3} and \ref{cor:Knn}. This Schema gives short certificates for s-factorisations for stability polynomials of all graphs of order $\leq 8$. \begin{center} \fbox{ \addtolength{\linewidth}{-2\fboxsep}% \addtolength{\linewidth}{-2\fboxrule}% \begin{minipage}{14cm} \begin{align*} A(G;p)=&(1-p)A(H_{1};p) + (1-p)A(H_{2};p) - (1-p)^2A(H_{3};p) &\text{~~~~~~(CS5)} \\ =&(1-p)A(H_{4};p)A(H_{5};p) + (1-p)A(H_{4};p)A(H_{6};p) \\ &-(1-p)^{2}A(H_{4};p)A(H_{7};p) &\text{~~~~(CS9)$\times$3} \\ =&A(H_{4};p) ((1-p)A(H_{5};p) + (1-p)A(H_{6};p)\\ &-(1-p)^{2}A(H_{7};p)) &\text{~(CS11)} \\ =&A(H_{4};p)A(H_{8};p) &\text{~~~~~~(CS6)} \end{align*} \begin{center} \textbf{Schema 2} \end{center} \end{minipage} } \end{center} The length of certificates constructed by Schema 2 is 6. This schema can be used to build the certificates of Theorems \ref{thm:Tn} and \ref{thm:GeneralSymmetry} and Corollaries \ref{thm:3} and \ref{cor:Knn}. \section{Conclusions and further work} This paper initiates an algebraic study for the stability polynomial, focusing on the fundamental algebraic properties of equality and factorisation. We gave upper bounds for lengths of certificates for stability equivalence and s-factorisations. There remains the challenge of determining better upper bounds, especially ones that do better than just, in effect, computing the polynomials. If a polynomial upper bound on certificate length can be found, then both those computational problems belong to NP. Determining whether this is the case remains an open problem. In this research we found short certificates for all s-factorisations of graphs of order 6 and one s-factorisation of graphs of order 7. This suggests the task of finding short certificates for s-factorisations of graphs of some higher orders. An open question that arises from this research is: what are the shortest certificates for infinite families of s-factorisations and stability equivalence? We found some short certificates but it is not known if these certificates are the shortest. Finding shortest certificates for infinite families of s-factorisations and stability equivalence could be challenging. \subsection*{Acknowledgements} We thank Ian Wanless for a suggestion that led to the proof of Theorem \ref{Thm:lengthOfSElowerBound}. This research was supported in part by the Australian Research Council's \textit{Discovery Projects} funding scheme (project number DP110100957). % CSG tried this to see if it would save a page, but it doesn't, % so leave it as is. %\SquashBibFurther \begin{thebibliography}{10} \bibitem{Birkhoff-1912-1913} G.H. Birkhoff. \newblock A determinant formula for the number of ways of coloring a map. \newblock {\em Ann. of Math.}, 14:42--46, 1912-1913. \bibitem{Bukovac-2013} Z.~Bukovac, G.~Farr, and K.~Morgan. \newblock Short certificates for chromatic equivalence. \newblock Submitted, 2013. \bibitem{Farr-1991} G.~Farr. \newblock The stability polynomial of a graph. \newblock (Unpublished manuscript), 1991. \bibitem{Farr-1993} G.~Farr. \newblock A correlation inequality involving stable set and chromatic polynomials. \newblock {\em J. Combin. Theory Ser. B}, 58:14--21, 1993. \bibitem{Farr-2011} G.~Farr. \newblock The chromatic polynomial and its relatives. \newblock (Unpublished manuscript), 2011. \bibitem{Gutman-1983} I.~Gutman and F.~Harary. \newblock Generalizations of the matching polynomial. \newblock {\em Utilitas Mathematica}, 24:97--106, 1983. \bibitem{Harary-1973} F.~Harary and E.M. Palmer. \newblock {\em Graphical Enumeration}. \newblock Academic Press, New York, 1973. \bibitem{Helgason-1974} T.~Helgason. \newblock {\em \textit{Aspects of the theory of hypermatroids}}, pages 191--213. \newblock Lecture Notes in Mathematics 411. Springer, Berlin, 1974. \bibitem{Morgan-2010} K.~Morgan. \newblock {\em Algebraic Aspects of the Chromatic Polynomial}. \newblock PhD thesis, Monash University, 2010. \bibitem{m-2009-17} K.~Morgan. \newblock Pairs of chromatically equivalent graphs. \newblock {\em Graphs Combin.}, 27:547--556, 2010. \bibitem{mf-2008-2} K.~Morgan and G.~Farr. \newblock {C}ertificates of factorisation for a class of triangle-free graphs. \newblock {\em Electron. J. Combin.}, 16:R75, 2009. \bibitem{Morgan-2009} K.~Morgan and G.~Farr. \newblock Certificates of factorisation for chromatic polynomials. \newblock {\em Electron. J. Combin.}, 16:R74, 2009. \bibitem{mf-2009-3} K.~Morgan and G.~Farr. \newblock Non-bipartite chromatic factors. \newblock {\em Discrete Mathematics}, 312:1166--1170, 2012. \bibitem{Reicher-1997} J.~Reicher. \newblock \textit{Computation of Stability Polynomials}. \newblock BCSE Hons dissertation, Monash University, 1997. \bibitem{Rosenfeld-2010} V.R. Rosenfeld. \newblock The independence polynomial of rooted products of graphs. \newblock {\em Discrete Appl. Math.}, 158:551--558, 2010. \end{thebibliography} \end{document}