Integer-root conjecture for total domination polynomials

A connected bipartite counterexample to the integer-root conjecture for total domination polynomials

Result. The conjecture is false. There exists a connected, simple, bipartite graph on 66 vertices and 105 edges, with minimum degree 2, whose total domination polynomial has the integer root $-4$ with multiplicity exactly two.

The statement being disproved is Conjecture 3.10 of S. Alikhani and N. Jafari, On the roots of total domination polynomial of graphs, arXiv:1605.02222; see also the published version by N. Jafari and S. Alikhani, Journal of Discrete Mathematical Sciences and Cryptography 23 (2020), 795–807, doi:10.1080/09720529.2019.1616908. The ordinary domination counterexample used as an ingredient is due to S. Alikhani and M. Griswold, On the Integer Domination Root Conjecture, arXiv:2608.00109, Theorem 2.1. Their theorem concerns ordinary domination polynomials; the argument below transfers it to the distinct conjecture about total domination.

1. A universal ordinary-to-total domination identity

Let $H=(V,E)$ be any finite simple graph. A subset $S\subseteq V$ dominates $H$ precisely when

$$N_H[v]\cap S\neq\varnothing\qquad(v\in V),$$

where $N_H[v]=\{v\}\cup N_H(v)$ is the closed neighborhood. Its ordinary domination polynomial is

$$D(H;x)=\sum_{S\text{ dominates }H}x^{|S|}.$$

Construct the bipartite closed-neighborhood double graph $B(H)$ with two disjoint copies $V_L$ and $V_R$ of $V$, inserting the edge $u_Lv_R$ exactly when

$$u=v\qquad\text{or}\qquad\{u,v\}\in E.$$

In particular, the diagonal pairs $v_Lv_R$ are ordinary edges between distinct vertices, not loops. The graph is simple, bipartite, and has

$$|V(B(H))|=2|V|, \qquad |E(B(H))|=|V|+2|E|, \qquad \deg_{B(H)}(v_L)=\deg_{B(H)}(v_R)=1+\deg_H(v).$$

Every $T\subseteq V(B(H))$ can be written uniquely as

$$T=(S_L)_L\cup(S_R)_R, \qquad S_L,S_R\subseteq V.$$

A left vertex $v_L$ has a neighbor in $T$ if and only if

$$N_H[v]\cap S_R\neq\varnothing,$$

and a right vertex $v_R$ has a neighbor in $T$ if and only if

$$N_H[v]\cap S_L\neq\varnothing.$$

Consequently, $T$ is a total dominating set of $B(H)$ if and only if $S_L$ and $S_R$ are two independently chosen ordinary dominating sets of $H$. Preservation of their cardinalities yields the polynomial identity

$$\boxed{\displaystyle D_t(B(H);x)=D(H;x)^2.}$$

Thus every ordinary domination root of every finite graph is a total domination root of a bipartite graph, with twice its original multiplicity. If $H$ is connected, then $B(H)$ is connected: each edge $uv\in E(H)$ gives the path $u_L-v_R-v_L$, and every right vertex is attached to its matching left vertex.

2. The explicit 33-vertex ingredient

Take the connected graph $H=G_{33}$ of Alikhani and Griswold, with vertex set $\{0,1,\ldots,32\}$ and edge set

$$\begin{aligned} E(H)=\{&\{0,1\},\{0,3\},\{0,4\},\{0,12\},\{1,2\},\{1,12\},\{1,18\},\\ &\{2,3\},\{2,6\},\{2,8\},\{2,10\},\{2,18\},\{2,21\},\{3,21\},\{3,24\},\\ &\{4,5\},\{6,7\},\{8,9\},\{10,11\},\{12,13\},\{12,14\},\{12,15\},\\ &\{12,16\},\{12,17\},\{18,19\},\{18,20\},\{21,22\},\{21,23\},\\ &\{24,25\},\{24,26\},\{26,27\},\{27,28\},\{28,29\},\{28,31\},\\ &\{29,30\},\{31,32\}\}. \end{aligned}$$

Their Theorem 2.1 establishes the exact factorization

$$D(H;x)=x^{11}(x+2)(x+4)(x^2+3x+1)Q_{18}(x),$$

where

$$\begin{aligned} Q_{18}(x)={}&x^{18}+24x^{17}+269x^{16}+1871x^{15}+9049x^{14} +32314x^{13}+88298x^{12}\\ &+188808x^{11}+320426x^{10}+435134x^9+474341x^8 +414314x^7\\ &+287750x^6+156593x^5+65228x^4+20061x^3 +4295x^2+573x+36. \end{aligned}$$

For completeness, this factorization can also be checked directly from the displayed edge set using a finite mathematical identity. Let $C$ be the set of non-leaf vertices, and let $t_v$ count the leaves adjacent to $v\in C$. Here

$$C=\{0,1,2,3,4,6,8,10,12,18,21,24,26,27,28,29,31\},$$

and, in that order,

$$(t_v)_{v\in C}=(0,0,0,0,1,1,1,1,5,2,2,1,0,0,0,1,1).$$

For $S\subseteq C$, every leaf adjacent to an unchosen vertex must itself be chosen; the leaves adjacent to a chosen vertex are free. An unchosen non-leaf vertex with no adjacent leaf must have a neighbor in $S$. Therefore the complete ordinary domination polynomial is exactly

$$D(H;x)= \sum_{\substack{S\subseteq C\\ N_H(v)\cap S\neq\varnothing\;\text{for every }v\in C\setminus S\text{ with }t_v=0}} x^{|S|} \prod_{v\in S}(1+x)^{t_v} \prod_{v\in C\setminus S}x^{t_v}.$$

Expanding this identity gives precisely the factorization above. In particular,

$$D(H;-4)=0, \qquad Q_{18}(-4)=26236000\neq0,$$

so the root $-4$ of $D(H;x)$ is simple.

3. The total-domination counterexample

Apply the universal identity to $B=B(H)$. Since $|V(H)|=33$, $|E(H)|=36$, and $\delta(H)=1$, this is a connected simple bipartite graph satisfying

$$|V(B)|=66, \qquad |E(B)|=33+2\cdot36=105, \qquad \delta(B)=2.$$

Its total domination polynomial is

$$\boxed{\displaystyle D_t(B;x)=x^{22}(x+2)^2(x+4)^2(x^2+3x+1)^2Q_{18}(x)^2. }$$

Hence $-4$ is an integer total domination root of multiplicity exactly two. Since

$$-4\notin\{-3,-2,-1,0\},$$

the integer-root conjecture for total domination polynomials is false, even when restricted to connected bipartite graphs of minimum degree at least two. This does not contradict the source's separate result for graphs satisfying the much stronger minimum-degree hypothesis $\delta(G)\geq 2|V(G)|/3$.