An independent set in a graph G is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial AΣx^(|A|), where the sum is over all independent sets A of G. In 1987, Alavi,Malde, Schwe...An independent set in a graph G is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial AΣx^(|A|), where the sum is over all independent sets A of G. In 1987, Alavi,Malde, Schwenk and Erd os conjectured that the independence polynomial of any tree or forest is unimodal.Although this unimodality conjecture has attracted many researchers’ attention, it is still open. Recently, Basit and Galvin even asked a much stronger question whether the independence polynomial of every tree is ordered log-concave. Note that if a polynomial has only negative real zeros then it is ordered log-concave and unimodal.In this paper, we observe real-rootedness of independence polynomials of rooted products of graphs. We find some trees whose rooted product preserves real-rootedness of independence polynomials. In consequence, starting from any graph whose independence polynomial has only real zeros, we can obtain an infinite family of graphs whose independence polynomials have only real zeros. In particular, applying it to trees or forests, we obtain that their independence polynomials are unimodal and ordered log-concave.展开更多
基金supported by the National Natural Science Foundation of China (Nos.11971206, 12022105)the Natural Science Foundation of Distinguished Young Scholars of Jiangsu Province (No.BK20200048)Postgraduate Research Practice&Innovation Program of Jiangsu Province (No.KYCX21-2565)。
文摘An independent set in a graph G is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial AΣx^(|A|), where the sum is over all independent sets A of G. In 1987, Alavi,Malde, Schwenk and Erd os conjectured that the independence polynomial of any tree or forest is unimodal.Although this unimodality conjecture has attracted many researchers’ attention, it is still open. Recently, Basit and Galvin even asked a much stronger question whether the independence polynomial of every tree is ordered log-concave. Note that if a polynomial has only negative real zeros then it is ordered log-concave and unimodal.In this paper, we observe real-rootedness of independence polynomials of rooted products of graphs. We find some trees whose rooted product preserves real-rootedness of independence polynomials. In consequence, starting from any graph whose independence polynomial has only real zeros, we can obtain an infinite family of graphs whose independence polynomials have only real zeros. In particular, applying it to trees or forests, we obtain that their independence polynomials are unimodal and ordered log-concave.
