TY - JOUR
ID - 760
TI - On the total domatic number of regular graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Aram, H.
AU - Sheikholeslami, S. M.
AU - Volkmann, L.
AD - Azarbaijan University of Tarbiat Moallem
AD - RWTH-Aachen University
Y1 - 2012
PY - 2012
VL - 1
IS - 1
SP - 45
EP - 51
KW - total dominating set
KW - total domination number
KW - total domatic number
KW - Regular graph
DO - 10.22108/toc.2012.760
N2 - 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))$.
UR - https://toc.ui.ac.ir/article_760.html
L1 - https://toc.ui.ac.ir/article_760_362cc9c41ad1def424bd149103450c49.pdf
ER -