| Naslov: | The independence polynomial of trees is not always log-concave starting from order 26 |
|---|
| Avtorji: | ID Kadrawi, Ohr (Avtor)
ID Levit, Vadim (Avtor) |
|---|
| Datoteke: |  AMC_Kadrawi,Levit_2025.pdf (352,77 KB)
MD5: 33798E9DA9D4EA14CC310C4442C69F03
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | tree, independent set, independence polynomial, unimodality, log-concavity |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 30.07.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 23 str. |
|---|
| Številčenje: | Vol. 25, no. 4, [article no.] P4.03 |
|---|
| PID: | 20.500.12556/RUP-22017  |
|---|
| UDK: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.3207.2ad |
|---|
| Datum objave v RUP: | 22.10.2025 |
|---|
| Število ogledov: | 552 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
