| Title: | The independence polynomial of trees is not always log-concave starting from order 26 |
|---|
| Authors: | ID Kadrawi, Ohr (Author)
ID Levit, Vadim (Author) |
|---|
| Files: |  AMC_Kadrawi,Levit_2025.pdf (352,77 KB)
MD5: 33798E9DA9D4EA14CC310C4442C69F03
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| 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 α(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) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave. |
|---|
| Keywords: | tree, independent set, independence polynomial, unimodality, log-concavity |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 30.07.2025 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 23 str. |
|---|
| Numbering: | Vol. 25, no. 4, [article no.] P4.03 |
|---|
| PID: | 20.500.12556/RUP-22017  |
|---|
| UDC: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.3207.2ad |
|---|
| Publication date in RUP: | 22.10.2025 |
|---|
| Views: | 553 |
|---|
| Downloads: | 2 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
