On the largest real root of the independence polynomial of a unicyclic graph

Iain Beaton, Ben Cameron

Published 2020-06-09Version 1

The independence polynomial of a graph $G$, denoted $I(G,x)$, is the generating polynomial for the number of independent sets of each size. The roots of $I(G,x)$ are called the \textit{independence roots} of $G$. It is known that for every graph $G$, the independence root of smallest modulus, denoted $\xi(G)$, is real. The relation $\preceq$ on the set of all graphs is defined as follows, $H\preceq G$ if and only if $I(H,x)\ge I(G,x)\text{ for all }x\in [\xi(G),0].$ We find the maximum and minimum connected unicyclic and connected well-covered unicyclic graphs of a given order with respect to $\preceq$. This extends recent work by Oboudi where the maximum and minimum trees of a given order were determined and also answers an open question posed in the same work. Corollaries of our results give the graphs that minimize and maximize $\xi(G)$ among all connected (well-covered) unicyclic graphs. We also answer more open questions posed by Oboudi and disprove a related conjecture due to Levit and Mandrescu.