Bipartition Polynomials, the Ising Model, and Domination in Graphs

Markus Dod; Tomer Kotek; James Preen; Peter Tittmann

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 335-353
  • ISSN: 2083-5892

Abstract

top
This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants. We apply this approach to show that, analogously to the Tutte polynomial, the Ising polynomial introduced by Andrén and Markström in [3], can be represented as a sum over spanning forests.

How to cite

top

Markus Dod, et al. "Bipartition Polynomials, the Ising Model, and Domination in Graphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 335-353. <http://eudml.org/doc/271088>.

@article{MarkusDod2015,
abstract = {This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants. We apply this approach to show that, analogously to the Tutte polynomial, the Ising polynomial introduced by Andrén and Markström in [3], can be represented as a sum over spanning forests.},
author = {Markus Dod, Tomer Kotek, James Preen, Peter Tittmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; Ising model; graph polynomial},
language = {eng},
number = {2},
pages = {335-353},
title = {Bipartition Polynomials, the Ising Model, and Domination in Graphs},
url = {http://eudml.org/doc/271088},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Markus Dod
AU - Tomer Kotek
AU - James Preen
AU - Peter Tittmann
TI - Bipartition Polynomials, the Ising Model, and Domination in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 335
EP - 353
AB - This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants. We apply this approach to show that, analogously to the Tutte polynomial, the Ising polynomial introduced by Andrén and Markström in [3], can be represented as a sum over spanning forests.
LA - eng
KW - domination; Ising model; graph polynomial
UR - http://eudml.org/doc/271088
ER -

References

top
  1. [1] W. Ahrens, Mathematische Unterhaltungen und Spiele (B.G. Teubner, Leipzig, Berlin, 1921). 
  2. [2] M. Aigner, A Course in Enumeration (Springer, Heidelberg, 2007). 
  3. [3] D. Andrén and K. Markström, The bivariate Ising polynomial of a graph, Discrete Appl. Math. 157 (2009) 2515-2524. doi:810.1016/j.dam.2009.02.021 [WoS] Zbl1211.05059
  4. [4] J.L. Arocha, Propiedades del polinomio independiente de un grafo, Ciencias Matemăticas 5 (1984) 103-110. 
  5. [5] J.L. Arocha and B. Llano, Meanvalue for the matching and dominating polynomial , Discuss. Math. Graph Theory 20 (2000) 57-69. doi:10.7151/dmgt.1106[Crossref] Zbl0958.05098
  6. [6] A.E. Brouwer, The number of dominating sets of a finite graph is odd, preprint, (2009). http://www.win.tue.nl/˜aeb/preprints/domin2.pdf. 
  7. [7] K. Dohmen and P. Tittmann, Domination reliability, Electron. J. Combin. 19(1) (2012) #15. Zbl1243.05183
  8. [8] J.A. Ellis-Monaghan and I. Moffatt, The Tutte-Potts connection in the presence of an external magnetic field, Adv. Appl. Math. 47 (2011) 772-782. doi:10.1016/j.aam.2011.02.004[Crossref][WoS] Zbl1232.05100
  9. [9] D. Garijo, A. Goodall and J. Nešetril, Distinguishing graphs by their left and right homomorphism profiles, European J. Combin. 32 (2011) 1025-1053. doi:10.1016/j.ejc.2011.03.012[Crossref] Zbl1230.05216
  10. [10] C. Godsil and I. Gutman, On the theory of the matching polynomial , J. Graph Theory 5 (1981) 137-144. doi:10.1002/jgt.3190050203[Crossref] Zbl0462.05051
  11. [11] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). doi:10.1007/978-1-4613-0163-9[Crossref] Zbl0968.05002
  12. [12] I. Gutman and F. Harary, Generalizations of the matching polynomial , Util. Math. 24 (1983) 97-106. Zbl0527.05055
  13. [13] O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Commun. Math. Phys. 25 (1972) 190-232. doi:10.1007/BF01877590[Crossref] Zbl0228.05131
  14. [14] C. Hoede and X.-L. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228. 10.1016/0012-365X(94)90163-5 
  15. [15] T. Kotek, Complexity of Ising polynomials, Combin. Probab. Comput. 21 (2012) 743-772. doi:10.1017/S0963548312000259[Crossref] Zbl1247.82011
  16. [16] T. Kotek, J. Preen and P. Tittmann, Subset-sum representations of domination polynomials, Graphs Combin. 30 (2014) 647-660. doi:10.1007/s00373-013-1286-z[Crossref] Zbl1291.05094
  17. [17] T. Kotek, J. Preen and P. Tittmann: Domination polynomials of graph products, submitted. 
  18. [18] K. Markström, The general graph homomorphism polynomial: Its relationship with other graph polynomials and partition functions, arXiv preprint arXiv:1401.6335 (2014). 
  19. [19] B. Mohar, Graph laplacians, in: Topics in Algebraic Graph Theory, L.W. Beineke and R.J. Wilson (Eds.), Cambridge University Press (2004) 113-136. Zbl1161.05334
  20. [20] A.D. Scott and G.B. Sorkin, Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function, ACM Transactions on Algorithms (TALG) 5 (2009) 4. doi:10.1145/1597036.1597049[Crossref][WoS] Zbl1298.68256
  21. [21] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math. 6 (1954) 80-91. doi:10.4153/CJM-1954-010-9[Crossref] Zbl0055.17101
  22. [22] J.M.M. van Rooij, Polynomial space algorithms for counting dominating sets and the domatic number, in: CIAC 2010, LNCS 6078, T. Calamoneri and J. Diaz (Eds.)(2010) 73-84. Zbl1284.05318

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.