
arXiv: 1802.02478
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.
05C31, 05C69, stable polynomial, graph, root, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph polynomials, FOS: Mathematics, Mathematics - Combinatorics, independence polynomial, Combinatorics (math.CO)
05C31, 05C69, stable polynomial, graph, root, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph polynomials, FOS: Mathematics, Mathematics - Combinatorics, independence polynomial, Combinatorics (math.CO)
| 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). | 3 | |
| 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 |
