Bivariate Domination Polynomial

James Preen 1, Alexander Murray 2
1Mathematics, Cape Breton University, Sydney, Nova Scotia, B1P 6L2, Canada.
2Karlsruher Institut für Technologie, Hermann-von-Helmholtz-Platz 1, Eggenstein-Leopoldshafen, Germany.

Abstract

We introduce a new bivariate polynomial
\[
J(G; x, y) := \sum_{W \subseteq V(G)} x^{|W|} y^{|N[W]| – |W|}
\]
which contains the standard domination polynomial of the graph \( G \) in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.