On the stability of independence polynomials (Q1753011): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:57, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the stability of independence polynomials |
scientific article |
Statements
On the stability of independence polynomials (English)
0 references
25 May 2018
0 references
Summary: 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.
0 references
graph
0 references
independent set
0 references
independence polynomial
0 references
stable polynomial
0 references
root
0 references