Bivariate Domination Polynomial

Abstract

We introduce a new bivariate polynomial $J(G;x,y):=\sum _{W\in V(G)}{x}^{|W|}{y}^{|N(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.

13 pages, 4 figures