August 2018, 1(3): 255-263. doi: 10.3934/mfc.2018011

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

Received  October 2017 Revised  January 2018 Published  July 2018

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.

Citation: Haisheng Tan, Liuyan Liu, Hongyu Liang. Total $\{k\}$-domination in special graphs. Mathematical Foundations of Computing, 2018, 1 (3) : 255-263. doi: 10.3934/mfc.2018011
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. BresarP. DorbecW. GoddardB. HartnellM. HenningS. 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. DomkeS. HedetniemiR. 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.

show all references

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. BresarP. DorbecW. GoddardB. HartnellM. HenningS. 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. DomkeS. HedetniemiR. 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.

[1]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295

[2]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201

[3]

Michael Hochman. Lectures on dynamics, fractal geometry, and metric number theory. Journal of Modern Dynamics, 2014, 8 (3&4) : 437-497. doi: 10.3934/jmd.2014.8.437

[4]

E. Muñoz Garcia, R. Pérez-Marco. Diophantine conditions in small divisors and transcendental number theory. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1401-1409. doi: 10.3934/dcds.2003.9.1401

[5]

Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071

[6]

Navin Keswani. Homotopy invariance of relative eta-invariants and $C^*$-algebra $K$-theory. Electronic Research Announcements, 1998, 4: 18-26.

[7]

L. Búa, T. Mestdag, M. Salgado. Symmetry reduction, integrability and reconstruction in $k$-symplectic field theory. Journal of Geometric Mechanics, 2015, 7 (4) : 395-429. doi: 10.3934/jgm.2015.7.395

[8]

A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial & Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233

[9]

Nigel Higson and Gennadi Kasparov. Operator K-theory for groups which act properly and isometrically on Hilbert space. Electronic Research Announcements, 1997, 3: 131-142.

[10]

Harsh Pittie and Arun Ram. A Pieri-Chevalley formula in the K-theory of aG/B-bundle. Electronic Research Announcements, 1999, 5: 102-107.

[11]

Jungho Park. Dynamic bifurcation theory of Rayleigh-Bénard convection with infinite Prandtl number. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 591-604. doi: 10.3934/dcdsb.2006.6.591

[12]

Francesco Cellarosi, Ilya Vinogradov. Ergodic properties of $k$-free integers in number fields. Journal of Modern Dynamics, 2013, 7 (3) : 461-488. doi: 10.3934/jmd.2013.7.461

[13]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547

[14]

Robert M. Strain. Coordinates in the relativistic Boltzmann theory. Kinetic & Related Models, 2011, 4 (1) : 345-359. doi: 10.3934/krm.2011.4.345

[15]

Krešimir Burazin, Marko Vrdoljak. Homogenisation theory for Friedrichs systems. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1017-1044. doi: 10.3934/cpaa.2014.13.1017

[16]

Ryszard Rudnicki. An ergodic theory approach to chaos. Discrete & Continuous Dynamical Systems - A, 2015, 35 (2) : 757-770. doi: 10.3934/dcds.2015.35.757

[17]

Philip Schrader. Morse theory for elastica. Journal of Geometric Mechanics, 2016, 8 (2) : 235-256. doi: 10.3934/jgm.2016006

[18]

Thierry de la Rue. An introduction to joinings in ergodic theory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 121-142. doi: 10.3934/dcds.2006.15.121

[19]

Luis Barreira. Dimension theory of flows: A survey. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3345-3362. doi: 10.3934/dcdsb.2015.20.3345

[20]

Jianjun Tian, Xiao-Song Lin. Colored coalescent theory. Conference Publications, 2005, 2005 (Special) : 833-845. doi: 10.3934/proc.2005.2005.833

 Impact Factor: 

Metrics

  • PDF downloads (27)
  • HTML views (232)
  • Cited by (0)

Other articles
by authors

[Back to Top]