On the total domatic number of regular graphs

Document Type: Research Paper

Authors

1 Azarbaijan University of Tarbiat Moallem

2 RWTH-Aachen University

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 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))$‎.

Keywords

Main Subjects


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