Some new results on the total domination polynomial of a graph

Abstract

Let $G=(V,E)$ be a simple graph of order $n$. The total dominating set of $G$ is a subset $D$ of $V$ that every vertex of $V$ is adjacent to some vertices of $D$. The total domination number of $G$ is equal to minimum cardinality of 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$. A root of $D_t(G,x)$ is called a total domination root of $G$. An irrelevant edge of $D_t(G,x)$ is an edge $e\in E$, such that $D_t(G,x)=D_t(G\setminus e,x)$. In this paper, we characterize edges possessing this property. Also we obtain some results for the number of total dominating sets of a regular graph. Finally, we study graphs with exactly two total domination roots $\{-3,0\}$, $\{-2,0\}$ and $\{-1,0\}$.

12 pages, 7 figures