Total $\{k\}$-domination in special graphs

Haisheng Tan; Liuyan Liu; Hongyu Liang

doi:10.3934/mfc.2018011

Article Contents

2018, Volume 1, Issue 3: 255-263. Doi: 10.3934/mfc.2018011

This issue Previous Article Influence analysis: A survey of the state-of-the-art Next Article Discrete heat transfer search for solving travelling salesman problem

Total $\{k\}$-domination in special graphs

1.
University of Science and Technology of China (USTC), Hefei, China
2.
Facebook Seattle, 1101 Dexter Ave N, Seattle, WA 98109, USA

* Corresponding author: Hongyu Liang. Email: hongyuliang86@gmail.com
* Corresponding author: Hongyu Liang. Email: hongyuliang86@gmail.com

Received: October 2017

Revised: January 2018

Published: July 2018

Abstract Full Text(HTML) Related Papers Cited by

Abstract

For a positive integer $k$ and a graph $G = (V,E)$, a function $f:V \to \{0,1,...,k\}$ is called a total $\{k\}$-dominating function of $G$ if $\sum_{u∈ N_G(v)}f(u)≥ k$ for each $v∈ V$, where $N_G(v)$ is the neighborhood of $v$ in $G$. The total $\{k\}$-domination number of $G$, denoted by $\gamma _t^{\left\{ k \right\}}\left( G \right)$, is the minimum weight of a total $\{k\}$-dominating function $G$, where the weight of $f$ is $\sum_{v∈ V}f(v)$. In this paper, we determine the exact values of the total $\{k\}$-domination number for several commonly-encountered classes of graphs including cycles, paths, wheels, and pans.

Keywords:

Mathematics Subject Classification: 05C10.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	H. Aram and S. Sheikholeslami, On the total $\{k\}$-domination and total $\{k\}$-domatic number of graphs, Bull. Malays. Math. Sci. Soc., 36 (2013), 39-47.
[2]	B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, Berlin, 1998. doi: 10.1007/978-1-4612-0619-4.
[3]	B. Bresar, P. Dorbec, W. Goddard, B. Hartnell, M. Henning, S. Klavzar and D. F. Rall, Vizing's conjecture: A survey and recent results, J. Graph Theory, 69 (2012), 46-76. doi: 10.1002/jgt.20565.
[4]	G. Domke, S. Hedetniemi, R. Laskar and G. Fricke, Relationships between integer and fractional parameters of graphs, Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial Conference on the Theory and Applications of Graphs (Kalamazoo, MI, 1988), 2 (1991), 371-387.
[5]	T. Haynes, S. H. ST and P. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, 1998.
[6]	T. Haynes, S. H. ST and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, 1998.
[7]	J. He and H. Liang, Complexity of total $\{k\}$-domination and related problems, Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, (eds. M. Atallah, X. -Y. Li and B. Zhu), vol. 6681 of LNCS, 2011,147–155. doi: 10.1007/978-3-642-21204-8_18.
[8]	M. A. Henning, A short proof of a result on a vizing-like problem for integer total domination, J. Comb. Optim., 20 (2010), 321-323. doi: 10.1007/s10878-008-9201-x.
[9]	C. Lee, Labelled Domination and Its Variants, PhD thesis, National Chung Cheng University, 2006.
[10]	N. Li and X. Hou, On the total $\{k\}$-domination number of Cartesian products of graphs, J. Comb. Optim., 18 (2009), 173-178. doi: 10.1007/s10878-008-9144-2.