On the stability of independence polynomials

MaRDI QIDQ1753011zbMATH OpenFDO

Authors Jason I. Brown, Ben Cameron

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02478, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p46

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graphindependence polynomialindependent setrootstable polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size, and its roots are called {em independence roots}. We investigate the stability of such polynomials, that is, conditions under which the roots lie in the left half-plane (all of the real roots of independence polynomial are negative and hence lie in this half-plane). We show stability for all independence polynomials of graphs with independence number at most three, but for larger independence number we show that the independence polynomials can have roots arbitrarily far to the right. We provide families of graphs whose independence polynomials are stable and ones that are not, utilizing various graph operations.

Recommendations

• The independence polynomial of rooted products of graphs
• Building graphs whose independence polynomials have only real roots
• On the location of roots of independence polynomials
• On the roots of expected independence polynomials
• On the rational independence roots

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 4202288 (Why is no real title available?)
• scientific article; zbMATH DE number 47002 (Why is no real title available?)
• scientific article; zbMATH DE number 528857 (Why is no real title available?)
• scientific article; zbMATH DE number 3445421 (Why is no real title available?)
• Average independence polynomials
• Homogeneous multivariate polynomials with the half-plane property
• Note on the smallest root of the independence polynomial
• On chromatic roots of large subdivisions of graphs
• On the location of roots of independence polynomials
• On the roots of independence polynomials of almost all very well-covered graphs
• On the unimodality of independence polynomials of very well-covered graphs
• Roots of independence polynomials of well covered graphs
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The roots of the independence polynomial of a clawfree graph
• Zeros of Reliability Polynomials and f-vectors of Matroids

Cited in

(22)

• Independence polynomials of circulants with an application to music
• Certificates for properties of stability polynomials of graphs
• On symmetry of independence polynomials
• On the location of roots of independence polynomials
• A note on purely imaginary independence roots
• Graphs whose independence fractals are line segments
• Building graphs whose independence polynomials have only real roots
• Maximum modulus of independence roots of graphs and trees
• Independence polynomials of bipartite graphs
• The independence fractal of a graph.
• Independence-preserving operations: effects in polynomial representations
• On a conjecture of Sokal concerning roots of the independence polynomial
• The independence polynomial of rooted products of graphs
• On the roots of expected independence polynomials
• Graph operations and partial unimodality of independence polynomials
• Average independence polynomials
• scientific article; zbMATH DE number 166023 (Why is no real title available?)
• Bounding the roots of independence polynomials.
• Generalizations of the matching polynomial to the multivariate independence polynomial
• Independence roots and independence fractals of certain graphs
• Stability for maximal independent sets
• Forests whose independence polynomials are palindromic and have only real roots

This page was built for publication: On the stability of independence polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753011)