On the total domatic number of regular graphs

Abstract

‎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 <em>total domatic number</em> 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-1$‎, ‎and that for 3-regular random graphs‎, ‎the‎ ‎total domatic number is almost surely equal to 2‎. ‎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/(3ln(r))$‎.