Geodesic
Some applications of Wagner's weighted subgraph counting polynomial
Ferenc Bencs ; Péter Csikvári1 ; Guus Regts2
1Alfred Renyi Institute of Mathematics
2Korteweg de Vries Institute for Mathematics, University of Amsterdam
The electronic journal of combinatorics, Tome 28 (2021) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $2^k$, 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.
DOI : 10.37236/10185
Classification : 05C31, 05C65, 05C35, 05C30
Mots-clés : antiferromagnetic Ising model, \(k\)-uniform hypergraph

Ferenc Bencs    ; Péter Csikvári  1   ; Guus Regts  2

1 Alfred Renyi Institute of Mathematics
2 Korteweg de Vries Institute for Mathematics, University of Amsterdam 
@article{10_37236_10185,
     author = {Ferenc Bencs and P\'eter Csikv\'ari and Guus Regts},
     title = {Some applications of {Wagner's} weighted subgraph counting polynomial},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {4},
     doi = {10.37236/10185},
     zbl = {1476.05087},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10185/}
}
TY  - JOUR
AU  - Ferenc Bencs
AU  - Péter Csikvári
AU  - Guus Regts
TI  - Some applications of Wagner's weighted subgraph counting polynomial
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10185/
DO  - 10.37236/10185
ID  - 10_37236_10185
ER  - 
%0 Journal Article
%A Ferenc Bencs
%A Péter Csikvári
%A Guus Regts
%T Some applications of Wagner's weighted subgraph counting polynomial
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/10185/
%R 10.37236/10185
%F 10_37236_10185
Ferenc Bencs; Péter Csikvári; Guus Regts. Some applications of Wagner's weighted subgraph counting polynomial. The electronic journal of combinatorics, Tome 28 (2021) no. 4. doi: 10.37236/10185

Cité par Sources :