On the total k-domination number of graphs

Adel P. Kazemi

Adel P. Kazemi

Discussiones Mathematicae Graph Theory, Tome 32 (2012), p. 419-426 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times 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] \cap S | \geq k$ . Also the total k-domination number $γ_{\times 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) \cap S | \geq 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, $γ_{\times k} (G) \leq γ_{\times k, t} (G) \leq n$ . Obviously for every k-regular graph, the upper bound n is sharp. Here, we give a sufficient condition for $γ_{\times k, t} (G) < n$ . Then we characterize complete multipartite graphs G with $γ_{\times k} (G) = γ_{\times 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.

Publié le : 2012-01-01

Zbl 1257.05117

EUDML-ID : urn:eudml:doc:270955

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1616,
     author = {Adel P. Kazemi},
     title = {On the total k-domination number of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {32},
     year = {2012},
     pages = {419-426},
     zbl = {1257.05117},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1616}
}

Adel P. Kazemi. On the total k-domination number of graphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 419-426. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1616/

Bibliographie

[000] [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. | Zbl 1168.05344

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

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

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

[004] [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. | Zbl 1210.05097

[005] [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.

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