Some Applications of Wagner's Weighted Subgraph Counting Polynomial
| Authors | |
|---|---|
| Publication date | 2021 |
| Journal | The Electronic Journal of Combinatorics |
| Article number | 4-14 |
| Volume | Issue number | 28 | 4 |
| Number of pages | 21 |
| Organisations |
|
| Abstract |
We use Wagner's weighted subgraph counting polynomial to prove that the partition function of the anti-ferromagnetic Ising model on line graphs is real rooted and to prove that roots of the edge cover polynomial have absolute value at most 4. We more generally show that roots of the edge cover polynomial of a k-uniform hypergraph have absolute value at most 2k, and discuss applications of this to the roots of domination polynomials of graphs. We moreover discuss how our results relate to efficient algorithms for approximately computing evaluations of these polynomials.
|
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.37236/10185 |
| Downloads |
Some Applications of Wagner's Weighted Subgraph Counting Polynomia
(Final published version)
|
| Permalink to this page | |