On the independent set polynomial of graphs and claw-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916897525596160 |
|---|---|
| author | Fialho, Paula M. S. Procacci, Aldo |
| author_facet | Fialho, Paula M. S. Procacci, Aldo |
| contents | We present two new contributions to the study of the independence polynomial $Z_G(z)$ of a finite simple graph $G = (V,E)$. First, we provide an improved lower bound for the zero-free region of $Z_G(z)$ for the important class of claw-free graphs. Our bound exceeds the classical Shearer radius and it is derived through a refined application of the Fernández-Procacci criterion using properties of the local neighborhood structure in claw-free graphs. Second, we establish a novel combinatorial expression for $Z_G(z)$, inspired by the connection with the abstract polymer gas models in statistical mechanics, which offers a new structural interpretation of the polynomial and may be of independent interest. These results strengthen the connection between statistical physics, combinatorics, and graph theory, and suggest new approaches for analytic exploration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22766 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the independent set polynomial of graphs and claw-free graphs Fialho, Paula M. S. Procacci, Aldo Combinatorics Mathematical Physics 05C31 We present two new contributions to the study of the independence polynomial $Z_G(z)$ of a finite simple graph $G = (V,E)$. First, we provide an improved lower bound for the zero-free region of $Z_G(z)$ for the important class of claw-free graphs. Our bound exceeds the classical Shearer radius and it is derived through a refined application of the Fernández-Procacci criterion using properties of the local neighborhood structure in claw-free graphs. Second, we establish a novel combinatorial expression for $Z_G(z)$, inspired by the connection with the abstract polymer gas models in statistical mechanics, which offers a new structural interpretation of the polynomial and may be of independent interest. These results strengthen the connection between statistical physics, combinatorics, and graph theory, and suggest new approaches for analytic exploration. |
| title | On the independent set polynomial of graphs and claw-free graphs |
| topic | Combinatorics Mathematical Physics 05C31 |
| url | https://arxiv.org/abs/2505.22766 |