Discussiones Mathematicae Graph Theory 32(3) (2012)
419-426

doi: 10.7151/dmgt.1616

## On the Total *k*-domination Number of Graphs

Adel P. Kazemi
Department of Mathematics University of Mohaghegh Ardabili P. O. Box 5919911367, Ardabil, Iran |

## Abstract

Let k be a positive integer and let G = (V,E) be a simple graph.
The k-tuple domination number γ_{×k}(G) of G is
the minimum cardinality
of a k-tuple dominating set S, a set that for every vertex v ∈ V, |N_{G}[v] ∩S | ≥ k. Also the total k-domination number
γ_{×k,t}(G) of G is the minimum cardinality of a total k
-dominating set S, a set that for every vertex v ∈ V,
|N_{G}(v) ∩S | ≥ k. The k-transversal number τ_{k}(H)
of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H).
We know that for any graph G of order n with minimum degree at
least k, γ_{×k}(G) ≤ γ_{×k,t}(G) ≤ n. Obviously for every k
-regular graph, the upper bound n is sharp. Here, we give a
sufficient condition for γ_{×k,t}(G) < n. Then we
characterize complete
multipartite graphs G with γ_{×k}(G) = γ_{×k,t}(G).
We also state that the total k-domination number of a graph is the k
-transversal number of its open neighborhood hypergraph, and also
the domination number of a graph is the transversal number of its
closed
neighborhood hypergraph. Finally, we give an upper bound for the total k
-domination number of the cross product graph G×H of two
graphs G and H in terms on the similar numbers of G and H.
Also, we show that this upper bound is strict for some graphs, when
k = 1.

**Keywords:** total *k*-domination (*k*-tuple total domination) number, *k*-tuple domination number, *k*-transversal number

**2010 Mathematics Subject Classification:** 05C69.

## References

[1] | M. El-Zahar, S. Gravier and A. Klobucar, * On the total domination number of cross products of graphs*, Discrete Math. ** 308** (2008) 2025--2029, doi: 10.1016/j.disc.2007.04.034 . |

[2] | F. Harary and T.W. Haynes, * Double domination in graphs*, Ars Combin. ** 55** (2000) 201--213. |

[3] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |

[4] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs; Advanced Topics (Marcel Dekker, New York, 1998). |

[5] | M.A. Henning and A.P. Kazemi, * **k*-tuple total domination in graphs, Discrete Appl. Math. ** 158** (2010) 1006--1011, doi: 10.1016/j.dam.2010.01.009. |

[6] | M.A. Henning and A.P. Kazemi, * **k*-tuple total domination in cross products of graphs, J. Comb. Optim. ** **{2011}, doi: 10.1007/s10878-011-9389-z. |

[7] | V. Chvátal and C. Mc Diarmid, * Small transversals in hypergraphs*, Combinatorica ** 12** (1992) 19--26, doi: 10.1007/BF01191201. |

Received 9 March 2011

Revised 23 July 2011

Accepted 25 July 2011