The total {k}-domatic number of digraphs

• Autorzy: Seyed Mahmoud Sheikholeslami , Lutz Volkmann
• Języki publikacji: EN

Abstrakty

EN

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}^d f_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ₜ^{{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.

Słowa kluczowe

EN

digraph; total {k}-dominating function; total {k}-domination number; total {k}-domatic number

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2012
• Tom: 32
• Numer: 3
• Strony: 461-471

Daty

wydano

2012

otrzymano

2011-03-31

poprawiono

2011-08-29

zaakceptowano

2011-08-30

Twórcy

autor

Seyed Mahmoud Sheikholeslami

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

autor

Lutz Volkmann

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1618