The independence polynomial of trees is not always log-concave starting from order 26

arXiv2305.01784MaRDI QIDQ6435110FDOQ6435110

Authors: Ohr Kadrawi, Vadim E. Levit 

Publication date: 2 May 2023

Abstract: An independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in $G$ is represented by $alpha(G)$. The independence polynomial of a graph $G=(V,E)$ was introduced by Gutman and Harary in 1983 and is defined as [ I(G;x) = sum_{k=0}^{alpha(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{alpha(G)}}x^{alpha(G)}, ] where $s_k$ represents the number of independent sets in $G$ of size $k$. The conjecture made by Alavi, Malde, Schwenk, and Erd"os in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this conjecture could be strengthened up to its corresponding log-concave version. However, in our paper, we present evidence that contradicts this assumption by introducing infinite families of trees whose independence polynomials are not log-concave.

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

This page was built for publication: The independence polynomial of trees is not always log-concave starting from order 26

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