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.
@article{bwmeta1.element.doi-10_7151_dmgt_1808,
author = {Markus Dod and Tomer Kotek and James Preen and Peter Tittmann},
title = {Bipartition Polynomials, the Ising Model, and Domination in Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {335-353},
zbl = {1311.05147},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1808}
}
Markus Dod; Tomer Kotek; James Preen; Peter Tittmann. Bipartition Polynomials, the Ising Model, and Domination in Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 335-353. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1808/
[1] W. Ahrens, Mathematische Unterhaltungen und Spiele (B.G. Teubner, Leipzig, Berlin, 1921).
[2] M. Aigner, A Course in Enumeration (Springer, Heidelberg, 2007).
[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] | Zbl 1211.05059
[4] J.L. Arocha, Propiedades del polinomio independiente de un grafo, Ciencias Matemăticas 5 (1984) 103-110.
[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] | Zbl 0958.05098
[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] K. Dohmen and P. Tittmann, Domination reliability, Electron. J. Combin. 19(1) (2012) #15. | Zbl 1243.05183
[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] | Zbl 1232.05100
[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] | Zbl 1230.05216
[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] | Zbl 0462.05051
[11] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). doi:10.1007/978-1-4613-0163-9[Crossref] | Zbl 0968.05002
[12] I. Gutman and F. Harary, Generalizations of the matching polynomial , Util. Math. 24 (1983) 97-106. | Zbl 0527.05055
[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] | Zbl 0228.05131
[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] T. Kotek, Complexity of Ising polynomials, Combin. Probab. Comput. 21 (2012) 743-772. doi:10.1017/S0963548312000259[Crossref] | Zbl 1247.82011
[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] | Zbl 1291.05094
[17] T. Kotek, J. Preen and P. Tittmann: Domination polynomials of graph products, submitted.
[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] B. Mohar, Graph laplacians, in: Topics in Algebraic Graph Theory, L.W. Beineke and R.J. Wilson (Eds.), Cambridge University Press (2004) 113-136. | Zbl 1161.05334
[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] | Zbl 1298.68256
[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] | Zbl 0055.17101
[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. | Zbl 1284.05318