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→{0,1,2} such that every vertex v with f(v)=0 satisfies ∑u∈ N(v)f(u)≥ 2; the \emph{Italian domination polynomial} DI(G,x)=∑k dI(G,k) xk records the number dI(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 dI(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 dI(Cn,2n−j), j=0,…,5, as trinomial coefficients minus explicitly enumerated forbidden configurations. On the algorithmic side, we give dynamic programming algorithms that compute \emph{all} coefficients of DI on path graphs (O(n2) time, O(n) space), on general trees (O(n2) time, O(n) space, via a post-order merge with a deficit parameter), and on cycle graphs (O(n2) time, O(n) space, via boundary conditioning), together with formal correctness proofs and complexity analyses. The known values γI(Pn)=⌊ n/2⌋+1 and γI(Cn)=⌈ n/2⌉ are recalled with references rather than reproved. All numerical results are verified against brute-force enumeration, and complete tables are provided.
Related
- DEPTH OF POWERS OF EDGE IDEALS OF CYCLES AND STARLIKE TREES
- The Ramsey threshold for trees versus odd cycles
- Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
- Counting hypergraphs without linear cycles of fixed length
- Curvature Diffusion of Inverse-weight Lin--Lu--Yau Ricci Flow on Finite Trees
BibTeX
@misc{shao2026counting,
title = {{Counting Weight-$k$ Italian Dominating Sets on Trees and Cycles}},
author = {Pingping Shao and Chengye Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00108},
eprint = {2610.00108},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00108},
}
RIS
TY - UNPB
TI - Counting Weight-k Italian Dominating Sets on Trees and Cycles
AU - Pingping Shao
AU - Chengye Zhao
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00108
UR - https://arxiv.org/abs/2610.00108
AB - 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→{0,1,2} such that every vertex v with f(v)=0 satisfies ∑_u∈ N(v)f(u)≥ 2; the \emph{Italian domination polynomial} D_I(G,x)=∑_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,…,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 γ_I(P_n)=⌊ n/2⌋+1 and γ_I(C_n)=⌈ n/2⌉ are recalled with references rather than reproved. All numerical results are verified against brute-force enumeration, and complete tables are provided.
ER -