DMGT

Discussiones Mathematicae Graph Theory 32(3) (2012) 461-471
DOI: https://doi.org/10.7151/dmgt.1618

The Total {k}-domatic Number of Digraphs

Seyed Mahmoud Sheikholeslami

Department of Mathematics
Azarbaijan University of Tarbiat Moallem
Tarbriz, I.R. Iran

Lutz Volkmann

Lehrstuhl II für Mathematik
RWTH Aachen University
52056 Aachen, Germany

Abstract

For a positive integer k, a total {k}-dominating function of a digraph D is a function f from the vertex set V(D) to the set {0,1,2, …,k} such that for any vertex v ∈ V(D), the condition ∑_{u ∈ N⁻(v)}f(u) ≥ k is fulfilled, where N⁻(v) consists of all vertices of D from which arcs go into v. A set {f₁,f₂, …,f_d} of total {k}-dominating functions of D with the property that ∑_{i = 1}^df_i(v) ≤ k for each v ∈ V(D), is called a total {k}-dominating family (of functions) on D. The maximum number of functions in a total {k}-dominating family on D is the total {k}-domatic number of D, denoted by d_t^{k}(D). Note that d_t^{1}(D) is the classic total domatic number d_t(D). In this paper we initiate the study of the total {k}-domatic number in digraphs, and we present some bounds for d_t^{k}(D). Some of our results are extensions of well-know properties of the total domatic number of digraphs and the total {k}-domatic number of graphs.

Keywords: digraph, total {k}-dominating function, total {k}-domination number, total {k}-domatic number

2010 Mathematics Subject Classification: 05C69.

References

[1]	H. Aram, S.M. Sheikholeslami and L. Volkmann, On the total {k}-domination and {k}-domatic number of a graph, Bull. Malays. Math. Sci. Soc. {to appear}{}{}} ().
[2]	J. Chen, X. Hou and N. Li, The total {k}-domatic number of wheels and complete graphs, J. Comb. Optim. {to appear}{}{}} ().
[3]	E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211--219, doi: 10.1002/net.3230100304.
[4]	E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi, Z. Shanchao and B. Xu, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000) 1--10, doi: 10.1016/S0012-365X(99)00251-4.
[5]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs (New York: Marcel Dekker, Inc., 1998).
[6]	K. Jacob and S. Arumugam, Domatic number of a digraph, Bull. Kerala Math. Assoc. 2 (2005) 93--103.
[7]	N. Li and X. Hou, On the total {k}-domination number of Cartesian products of graphs, J. Comb. Optim. 18 (2009) 173--178, doi: 10.1007/s10878-008-9144-2.
[8]	S.M. Sheikholeslami and L. Volkmann, The total {k}-domatic number of a graph, J. Comb. Optim. 23 (2012) 252--260, doi: 10.1007/s10878-010-9352-4.

Received 31 March 2011
Revised 29 August 2011
Accepted 30 August 2011