On $\mathcal{D}$-equivalence classes of some graphs

Abstract

Let $G$ be a simple graph of order $n$. The domination polynomial of $G$ is the polynomial $D(G,x)={\sum }_{i=1}^{n}d(G,i)x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. The $n$-barbell graph $Ba{r}_n$ with $2n$ vertices, is formed by joining two copies of a complete graph $K_n$ by a single edge. We prove that for every $n\ge 2$, $Ba{r}_n$ is not $\mathcal{D}$-unique, that is, there is another non-isomorphic graph with the same domination polynomial. More precisely, we show that for every $n$, the $\mathcal{D}$-equivalence class of barbell graph, $[Ba{r}_n]$, contains many graphs, which one of them is the complement of book graph of order $n-1$, $B_{n-1}^c$. Also we present many families of graphs in $\mathcal{D}$-equivalence class of $K_{n_1}\cup K_{n_2}\cup \cdots \cup K_{n_k}$.

arXiv comment9 pages, 5 figures

References in corpus (1)

• Complete r-partite graphs determined by their domination polynomial