On the total k-domination number of graphs

• Autorzy: Adel P. Kazemi
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

total k-domination (k-tuple total domination) number; k-tuple domination number; k-transversal 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: 419-426

Daty

wydano

2012

otrzymano

2011-03-09

poprawiono

2011-07-23

zaakceptowano

2011-07-25

Twórcy

autor

Adel P. Kazemi

• Department of Mathematics, University of Mohaghegh Ardabili, P.O. Box 5919911367, Ardabil, Iran

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1616