Domination polynomial of clique cover product of 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$. For two graphs $G$ and $H$, let $\mathcal{C}=\{C_1,C_2,\cdots ,C_k\}$ be a clique cover of $G$ and $U\subseteq V(H)$. We consider clique cover product which denoted by $G^{\mathcal{C}}\star H^U$ and obtained from $G$ as follows: for each clique $C_i\in \mathcal{C}$, add a copy of the graph $H$ and join every vertex of $C_i$ to every vertex of $U$. We prove that the domination polynomial of clique cover product $G^{\mathcal{C}}\star H^{V(H)}$ or simply $G^{\mathcal{C}}\star H$ is \[ D(G^\mathcal{C} \star H,x)=\prod_{i=1}^k\Big [\big((1+x)^{n_i}-1\big)(1+x)^{|V(H)|}+D(H,x)\Big], \] where each clique $C_i\in \mathcal{C}$ has $n_i$ vertices. As results, we study the $\mathcal{D}$-equivalence classes of some families of graphs. Also we completely describe the $\mathcal{D}$-equivalence classes of friendship graphs constructed by coalescence $n$ copies of the cycle graph of length three with a common vertex.

11 pages, 5 figures