More on total domination polynomial and $\mathcal{D}_t$-equivalence classes of some graphs

Document Type : Original Manuscript


Yazd University



Let $G = (V, E)$ be a simple graph of order $n$. A total dominating set of $G$ is a subset $D$ of $V$ such that every vertex of $V$ is adjacent to some vertices of $D$. The total domination number of $G$ is equal to the minimum cardinality of a total dominating set in $G$ and is denoted by $\gamma_t(G)$. The total domination polynomial of $G$ is the polynomial $D_t(G,x)=\sum_{i=\gamma_t(G)}^n d_t(G,i)x^i$, where $d_t(G,i)$ is the number of total dominating sets of $G$ of size $i$. Two graphs $G$ and $H$ are said to be total dominating equivalent or simply $\mathcal{D}_t$-equivalent, if $D_t(G,x)=D_t(H,x)$. The equivalence class of $G$, denoted $[G]$, is the set of all graphs $\mathcal{D}_t$-equivalent to $G$. A polynomial $\sum_{k=0}^n a_kx^k$ is called unimodal if the sequence of its coefficients is unimodal, that means there is some $k \in \{0, 1, \ldots , n\}$, such that $a_0 \leq \ldots \leq a_{k-1} \leq a_k\geq a_{k+1} \geq \ldots \geq a_n$. In this paper, we investigate $\mathcal{D}_t$-equivalence classes of some graphs. Also, we introduce some families of graphs whose total domination polynomials are unimodal.
The $\mathcal{D}_t$-equivalence classes of graphs of order $\leq 6$ are presented in the appendix.