On the total domatic number of regular graphs

‎A set S of vertices of a graph G=(V,E) without isolated vertex‎ ‎is a total dominating set if every vertex of V(G) is‎ ‎adjacent to some vertex in S‎. ‎The total domatic number of‎ ‎a graph G is the maximum number of total dominating sets into‎ ‎which the vertex set of G can be partitioned‎. ‎We show that the‎ ‎total domatic number of a random r-regular graph is almost‎ ‎surely at most r-۱‎, ‎and that for ۳-regular random graphs‎, ‎the‎ ‎total domatic number is almost surely equal to ۲‎. ‎We also give a‎ ‎lower bound on the total domatic number of a graph in terms of‎ ‎order‎, ‎minimum degree and maximum degree‎. ‎As a corollary‎, ‎we‎ ‎obtain the result that the total domatic number of an r-regular‎ ‎graph is at least r/(۳\ln(r))‎.

Keywords:

total dominating set , total domination number , total domatic number , Regular graph