2024/06/27 by Alikhani, Saeid, Bakhshesh, Davood, Ghanbari, Nima
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.00103
A subset of vertices S of a graph G is a dominating set if every vertex in V ∖ 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)=∑i=1d(G)dp(G,i)xi 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.