Some Applications of Wagner's Weighted Subgraph Counting Polynomial

Open Access
Authors
Publication date 2021
Journal The Electronic Journal of Combinatorics
Article number 4-14
Volume | Issue number 28 | 4
Number of pages 21
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
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
Permalink to this page
Back