On $D$-Equivalence Class of Complete Bipartite Graphs

Abstract

Let $G$ be a simple graph of order $n$. We define a dominating set as a set $S\subseteq V(G)$ such that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The $dominationpolynomial$ of $G$ is $D(G,x)=\sum _{i=0}^{n}d(G,i)x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. Two graphs $G$ and $H$ are $D-equivalent$, denoted $G\sim H$, if $D(G,x)=D(H,x)$. The $D-equivalenceclass$ of $G$ is $[G]=\{H\mid H\sim G\}$. Recently, determining the $D$-equivalence class of a given graph has garnered interest. In this paper, we show that for $n\ge 3$, $[K_{n,n}]$ has size two. We conjecture that the complete bipartite graph $K_{m,n}$ for $m,n\ge 2$ is uniquely determined by its domination polynomial.