Discussiones Mathematicae Graph Theory 32(3) (2012)
419-426
DOI: https://doi.org/10.7151/dmgt.1616
On the Total k-domination Number of Graphs
| Adel P. Kazemi
Department of Mathematics |
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, |NG[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, |NG(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
Close