The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size and its roots are called independence roots. We investigate the stability of such polynomials, that is, conditions under which the independence roots lie in the left half-plane. We use results from complex analysis to determine graph operations that result in a stable or nonstable independence polynomial. In particular, we prove that every graph is an induced subgraph of a graph with stable independence polynomial. We also show that the independence polynomials of graphs with independence number at most three are necessarily stable, but for larger independence number, we show that the independence polynomials can have roots arbitrarily far to the right.
@article{10_37236_7280,
author = {Jason I. Brown and Ben Cameron},
title = {On the stability of independence polynomials},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7280},
zbl = {1391.05136},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7280/}
}
TY - JOUR
AU - Jason I. Brown
AU - Ben Cameron
TI - On the stability of independence polynomials
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7280/
DO - 10.37236/7280
ID - 10_37236_7280
ER -
%0 Journal Article
%A Jason I. Brown
%A Ben Cameron
%T On the stability of independence polynomials
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7280/
%R 10.37236/7280
%F 10_37236_7280
Jason I. Brown; Ben Cameron. On the stability of independence polynomials. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7280
