Fetching the paper…

Reading the bibliography…

2017

On trees with real rooted independence polynomial

Bencs, Ferenc

Original
PDF
Post on X

Understand

The independence polynomial of a graph $G$ is \[I(G,x)=\sum\limits_{k\ge 0}i_k(G)x^k,\] where $i_k(G)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0(G)=1$).

In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.
In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu's theorem), caterpillars (Wang and Zhu's theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.

On trees with real rooted independence polynomial · Around

Built on

Log-concave and unimodal sequences in algebra, combinatorics, and geometry, 1989
R. P. Stanley · 1989
Earlier work this paper cites.
Algebraic combinatorics
C. D. Godsil · 1993
Earlier work this paper cites.
The independence polynomial of a graph-a survey
V. E. Levit and E. Mandrescu · 2005
Earlier work this paper cites.
The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma
A. Scott and A. Sokal · 2005
Earlier work this paper cites.

Similar

Counting independent sets up to the tree threshold
D. Weitz · 2006
Cited alongside, same era.
The roots of the independence polynomial of a clawfree graph
M. Chudnovsky and P. Seymour · 2007
Cited alongside, same era.
The Fibonacci number of Fibonacci trees and a related family of polynomial recurrence systems
S. G. Wagner · 2007
Cited alongside, same era.
The unimodality of independence polynomials of some graphs
Z. F. Zhu · 2007
Cited alongside, same era.

Then

On the unimodality of independence polynomials of some graphs
Y. Wang and B. X. Zhu · 2011
Later among the works it cites.
On the unimodality of independence polynomial of certain classes of graphs
S. Alikhani and F. Jafari · 2013
Later among the works it cites.
Unimodality of the independence polynomials of some composite graphs
B. X. Zhu and Q. Lu · 2015
Later among the works it cites.
The independent set sequence of some families of trees,
Original
D. Galvin and J. Hilyard · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…