آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 126 |
| تعداد مقالات | 1,601 |
| تعداد مشاهده مقاله | 1,813,360 |
| تعداد دریافت فایل اصل مقاله | 1,684,555 |
Counting the number of domatic partitions of specific graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 11 بهمن 1404 اصل مقاله (483.71 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31164.2765 | ||
| نویسندگان | ||
| Pedram Asadzadeh1؛ Saeid Alikhani* 2 | ||
| 1Department of Computer Engineering, K. N. Toosi University of Technology, P.O.Box 16765-3381, Tehran, Iran | ||
| 2Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| domatic partition, domatic number, dominating set؛ polynomial | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 122 تعداد دریافت فایل اصل مقاله: 148 |
||