Counting the number of domatic partitions of specific graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Computer Engineering, K. N. Toosi University of Technology, P.O.Box 16765-3381, Tehran, Iran

2 Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

Abstract

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. We consider the number of domatic partitions of $G$ with different sizes. Inspired by existing results for trees, this paper extends the analysis to several other important families of graphs. We focus primarily on the coefficient $dp(G,2)$, which counts domatic 2-partitions. We present some recurrence relations for this coefficient for the cycle graphs $C_n$ and the wheel graphs $W_n$. Furthermore, we present precise closed-form formulas for the domatic polynomial of star graphs $K_{1,n}$ and friendship graphs $F_n$. We also derive a formula for $dp(K_{m,n}, 2)$ for complete bipartite graphs. Finally, through a comprehensive computational analysis of all $3$-regular graphs of order $10$, we observe that the Petersen graph cannot be determined by its domatic polynomial.

Keywords

Main Subjects

References

[1] S. Alikhani, D. Bakhshesh, and N. Ghanbari, Counting the number of domatic partition of trees based on weak 2-coloring number, arXiv preprint arXiv:2403.10320 (2024).
[2] S. Alikhani and Y.H. Peng, Domination polynomials of cubic graphs of order 10, Turk. J. Math. 35 (2011), no. 3, 355–366. https://doi.org/10.3906/mat-1002-141
[3] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261.
https://doi.org/10.1002/net.3230070305
[4] T. Koshy, Fibonacci and Lucas Numbers with Applications, vol. 2, John Wiley & Sons, 2019.
[5] M. Landete and J.L. Sainz-Pardo, The domatic partition problem in separable graphs, Mathematics 10 (2022), no. 4, 640. https://doi.org/10.3390/math10040640
[6] T.L. Lu, P.H. Ho, and G.J. Chang, The domatic number problem in interval graphs, SIAM J. Discrete Math. 3 (1990), no. 4, 531–536. https://doi.org/10.1137/0403045
[7] S.L. Peng and M.S. Chang, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Inf. Process. Lett. 43 (1992), no. 6, 297–300. https://doi.org/10.1016/0020-0190(92)90115-C
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 31 January 2026

Files

Share

How to cite

Statistics