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 \({domination\; polynomial}\) 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-equivalence\; class}\) 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 \geq 3\), \([K_{n,n}]\) has size two. We conjecture that the complete bipartite graph \(K_{m,n}\) for \(m, n \geq 2\) is uniquely determined by its domination polynomial.