Counting Weight-$k$ Italian Dominating Sets on Trees and Cycles

Abstract

We study the problem of counting \emph{Italian dominating functions} (IDFs) of each possible weight on paths, trees, and cycles. An Italian dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ such that every vertex $v$ with $f(v)=0$ satisfies ${\sum }_{u\in N(v)}f(u)\ge 2$; the \emph{Italian domination polynomial} $D_I(G,x)={\sum }_k{d}_I(G,k)x^k$ records the number $d_I(G,k)$ of such functions of weight~$k$. This polynomial is the Italian analogue of the well-studied domination and Roman domination polynomials, and computing its coefficients on a fixed graph class is, in essence, a \emph{constrained integer composition} problem: passing to the deficit variables $y(v)=2-f(v)$, each coefficient $d_I(G,2n-j)$ counts the number of compositions of $j$ into $n$ parts, each at most~$2$, that additionally satisfy a local adjacency capacity constraint. We make this connection explicit and use it to derive closed-form expressions for $d_I(C_n,2n-j)$, $j=0,\dots ,5$, as trinomial coefficients minus explicitly enumerated forbidden configurations. On the algorithmic side, we give dynamic programming algorithms that compute \emph{all} coefficients of $D_I$ on path graphs ($O(n^2)$ time, $O(n)$ space), on general trees ($O(n^2)$ time, $O(n)$ space, via a post-order merge with a deficit parameter), and on cycle graphs ($O(n^2)$ time, $O(n)$ space, via boundary conditioning), together with formal correctness proofs and complexity analyses. The known values ${\gamma }_I(P_n)=\lfloor n/2\rfloor +1$ and ${\gamma }_I(C_n)=\lceil n/2\rceil$ are recalled with references rather than reproved. All numerical results are verified against brute-force enumeration, and complete tables are provided.

arXiv comment31 pages,0 figures