Counting the Number of Domatic Partition of a Graph
<|reference_start|>Counting the Number of Domatic Partition of a Graph: A subset of vertices $S$ of a graph $G$ is a dominating set if every vertex in $V \setminus S$ has at least one neighbor in $S$. A domatic partition is a partition of the vertices of a graph $G$ into disjoint dominating sets. The domatic number $d(G)$ is the maximum size of a domatic partition. Suppose that $dp(G,i)$ is the number of distinct domatic partition of $G$ with cardinality $i$. In this paper, we consider the generating function of $dp(G,i)$, i.e., $DP(G,x)=\sum_{i=1}^{d(G)}dp(G,i)x^i$ which we call it the domatic partition polynomial. We explore the domatic polynomial for trees, providing a quadratic time algorithm for its computation based on weak 2-coloring numbers. Our results include specific findings for paths and certain graph products, demonstrating practical applications of our theoretical framework.<|reference_end|>
@article{alikhani2024counting,
    title={Counting the Number of Domatic Partition of a Graph},
    author={Saeid Alikhani, Davood Bakhshesh and Nima Ghanbari},
    journal={arXiv preprint arXiv:2407.00103},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00103},
    primaryClass={math.CO cs.DM}
}