In Autumn 2020, DOAJ will be relaunching with a new website with updated functionality, improved search, and a simplified application form. More information is available on our blog. Our API is also changing.

Hide this message

Bipartition Polynomials, the Ising Model, and Domination in Graphs

Discussiones Mathematicae Graph Theory. 2015;35(2):335-353 DOI 10.7151/dmgt.1808


Journal Homepage

Journal Title: Discussiones Mathematicae Graph Theory

ISSN: 2083-5892 (Online)

Publisher: Sciendo

Society/Institution: University of Zielona Góra

LCC Subject Category: Science: Mathematics

Country of publisher: Poland

Language of fulltext: English

Full-text formats available: PDF



Dod Markus (Faculty Mathematics, Sciences, Computer Science University of Applied Sciences Mittweida)

Kotek Tomer (Institut für Informationssysteme 184/4 Technische Universität Wien, Vienna, Austria)

Preen James (Mathematics Cape Breton University Sydney, Canada)

Tittmann Peter (Faculty Mathematics, Sciences, Computer Science University of Applied Sciences Mittweida)


Blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 53 weeks


Abstract | Full Text

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.