The total {k}-domatic number of digraphs
Seyed Mahmoud Sheikholeslami ; Lutz Volkmann
Discussiones Mathematicae Graph Theory, Tome 32 (2012), p. 461-471 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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₂,...,fd of total k-dominating functions of D with the property that ∑i=1dfi(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ₜk(D). Note that dₜ1(D) is the classic total domatic number dₜ(D). In this paper we initiate the study of the total k-domatic number in digraphs, and we present some bounds for dₜ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.

Publié le : 2012-01-01
EUDML-ID : urn:eudml:doc:271065 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1618,
     author = {Seyed Mahmoud Sheikholeslami and Lutz Volkmann},
     title = {The total {k}-domatic number of digraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {32},
     year = {2012},
     pages = {461-471},
     zbl = {1257.05123},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1618}
}

Seyed Mahmoud Sheikholeslami; Lutz Volkmann. The total {k}-domatic number of digraphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 461-471. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1618/

[000] [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). | Zbl 1261.05074

[001] [2] J. Chen, X. Hou and N. Li, The total {k}-domatic number of wheels and complete graphs, J. Comb. Optim. (to appear). | Zbl 1283.90043

[002] [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. | Zbl 0447.05039

[003] [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. | Zbl 0954.05037

[004] [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs (New York: Marcel Dekker, Inc., 1998). | Zbl 0890.05002

[005] [6] K. Jacob and S. Arumugam, Domatic number of a digraph, Bull. Kerala Math. Assoc. 2 (2005) 93-103.

[006] [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. | Zbl 1193.05128

[007] [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. | Zbl 1243.90229