Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 2 | 335-353

Tytuł artykułu

Bipartition Polynomials, the Ising Model, and Domination in Graphs

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
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.

Słowa kluczowe

Wydawca

Rocznik

Tom

35

Numer

2

Strony

335-353

Opis fizyczny

Daty

wydano
2015-05-01
otrzymano
2014-01-23
poprawiono
2014-09-16
zaakceptowano
2014-09-16
online
2015-04-18

Twórcy

autor
  • Faculty Mathematics, Sciences, Computer Science University of Applied Sciences Mittweida
autor
  • Institut für Informationssysteme 184/4 Technische Universität Wien, Vienna, Austria
autor
  • Mathematics Cape Breton University Sydney, Canada
  • Faculty Mathematics, Sciences, Computer Science University of Applied Sciences Mittweida

Bibliografia

  • [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]
  • [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]
  • [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.
  • [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]
  • [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]
  • [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]
  • [11] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). doi:10.1007/978-1-4613-0163-9[Crossref]
  • [12] I. Gutman and F. Harary, Generalizations of the matching polynomial , Util. Math. 24 (1983) 97-106.
  • [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]
  • [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]
  • [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]
  • [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.
  • [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]
  • [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]
  • [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.

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.doi-10_7151_dmgt_1808
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.