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-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/(3\ln(r))$.
N. Alon (1990). Transversal numbers of uniform hypergraphs. Graphs Combin.. 6, 1-4 S. Arumugam and A. Thuraiswamy (1998). Total domatic number of a graph. Indian J. Pure Appl. Math.. 29, 513-515 E. A. Bender and E. R. Canfield (1978). The asymptotic number of labeled
graphs with given degree sequences. J. Combin. Theory Ser. A. 24, 296-307 I. Bouchemakh and S. Ouatiki (2009). On the domatic and the total domatic numbers of
the 2-section graph of the order-interval hypergraph of a finite
poset. Discrete Math.. 309, 3674-3679 E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi (1980). Total domination in graphs. Networks. 10, 211-219 P. Dankelmann, N. J. Calkin (2004). The Domatic Number of Regular Graphs. Ars Combin.. 73, 247-255 T. W. Haynes, S. T. Hedetniemi, P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York. T. W. Haynes, S. T. Hedetniemi, P. J. Slater, editors (1998). Domination in Graphs,
Advanced Topics. Marcel Dekker, Inc., New York. D. B. West (2000). Introduction to Graph Theory. Prentice-Hall, Inc. N. C. Wormald (1999). Models of Random Regular Graphs. In: Surveys in
Combinatorics 1999 (J.D. Lamb and D.A. Preece, eds.),
London Mathematical Society Lecture Notes Series , Cambridge
University Press, Cambridge. 267, 239-298 B. Zelinka (1988). Total domatic number of cacti. Math. Slovaca. 38, 207-214 B. Zelinka (1989). Total domatic number and degrees of vertices of a graph. Math. Slovaca. 39, 7-11
Aram, H., Sheikholeslami, S. M., & Volkmann, L. (2012). On the total domatic number of regular graphs. Transactions on Combinatorics, 1(1), 45-51. doi: 10.22108/toc.2012.760
MLA
H. Aram; S. M. Sheikholeslami; L. Volkmann. "On the total domatic number of regular graphs". Transactions on Combinatorics, 1, 1, 2012, 45-51. doi: 10.22108/toc.2012.760
HARVARD
Aram, H., Sheikholeslami, S. M., Volkmann, L. (2012). 'On the total domatic number of regular graphs', Transactions on Combinatorics, 1(1), pp. 45-51. doi: 10.22108/toc.2012.760
VANCOUVER
Aram, H., Sheikholeslami, S. M., Volkmann, L. On the total domatic number of regular graphs. Transactions on Combinatorics, 2012; 1(1): 45-51. doi: 10.22108/toc.2012.760
)
