2021/01/17 by Ron Yosef, Yosef, Ron, Matan Mizrachi +3
Computer Science · Mathematics · #05C05 #05C31 (Primary) 05C60 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph theory and applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2101.06744
openalex publication_date 2021/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An independent set in a graph is a set of pairwise non-adjacent vertices. The independence number α(G) is the size of a maximum independent set in the graph G. The independence polynomial of a graph is the generating function for the sequence of numbers of independent sets of each size. In other words, the k-th coefficient of the independence polynomial equals the number of independent sets comprised of k vertices. For instance, the degree of the independence polynomial of the graph G is equal to α(G). In 1987, Alavi, Malde, Schwenk, and Erdös conjectured that the independence polynomial of a tree is unimodal. In what follows, we provide support to this assertion considering trees with up to 20 vertices. Moreover, we show that the corresponding independence polynomials are log-concave and, consequently, unimodal. The algorithm computing the independence polynomial of a given tree makes use of a database of non-isomorphic unlabeled trees to prevent repeated computations.