# On the total k-domination number of graphs

• Volume: 32, Issue: 3, page 419-426
• ISSN: 2083-5892

top

## Abstract

top
Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number ${\gamma }_{×k}\left(G\right)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $|{N}_{G}\left[v\right]\cap S|\ge k$. Also the total k-domination number ${\gamma }_{×k,t}\left(G\right)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $|{N}_{G}\left(v\right)\cap S|\ge k$. The k-transversal number τₖ(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, ${\gamma }_{×k}\left(G\right)\le {\gamma }_{×k,t}\left(G\right)\le n$. Obviously for every k-regular graph, the upper bound n is sharp. Here, we give a sufficient condition for ${\gamma }_{×k,t}\left(G\right). Then we characterize complete multipartite graphs G with ${\gamma }_{×k}\left(G\right)={\gamma }_{×k,t}\left(G\right)$. 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.

## How to cite

top

Adel P. Kazemi. "On the total k-domination number of graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 419-426. <http://eudml.org/doc/270955>.

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 τₖ(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.},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total k-domination (k-tuple total domination) number; k-tuple domination number; k-transversal number; total -domination number; -tuple total domination number; -tuple domination number; -transversal number},
language = {eng},
number = {3},
pages = {419-426},
title = {On the total k-domination number of graphs},
url = {http://eudml.org/doc/270955},
volume = {32},
year = {2012},
}

TY - JOUR
TI - On the total k-domination number of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 419
EP - 426
AB - 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 τₖ(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.
LA - eng
KW - total k-domination (k-tuple total domination) number; k-tuple domination number; k-transversal number; total -domination number; -tuple total domination number; -tuple domination number; -transversal number
UR - http://eudml.org/doc/270955
ER -

## References

top
1. [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. Zbl1168.05344
2. [2] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. Zbl0993.05104
3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
4. [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs; Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
5. [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. Zbl1210.05097
6. [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. [7] V. Chvátal and C. Mc Diarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26, doi: 10.1007/BF01191201. Zbl0776.05080

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.