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.   Google Scholar

[2]

B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, Berlin, 1998. doi: 10.1007/978-1-4612-0619-4.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[5]

T. Haynes, S. H. ST and P. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, 1998. Google Scholar

[6]

T. Haynes, S. H. ST and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, 1998.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C. Lee, Labelled Domination and Its Variants, PhD thesis, National Chung Cheng University, 2006. Google Scholar

[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.  Google Scholar

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.   Google Scholar

[2]

B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, Berlin, 1998. doi: 10.1007/978-1-4612-0619-4.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[5]

T. Haynes, S. H. ST and P. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, 1998. Google Scholar

[6]

T. Haynes, S. H. ST and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, 1998.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C. Lee, Labelled Domination and Its Variants, PhD thesis, National Chung Cheng University, 2006. Google Scholar

[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.  Google Scholar

[1]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

[2]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[3]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054

[4]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[5]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[6]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310

[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[8]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127

[9]

Van Duong Dinh. Random data theory for the cubic fourth-order nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020284

[10]

Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, A pricing option approach based on backward stochastic differential equation theory. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 969-969. doi: 10.3934/dcdss.2019065

[11]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[12]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066

[13]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295

[14]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325

[15]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067

[16]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[17]

Bao Wang, Alex Lin, Penghang Yin, Wei Zhu, Andrea L. Bertozzi, Stanley J. Osher. Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training. Inverse Problems & Imaging, 2021, 15 (1) : 129-145. doi: 10.3934/ipi.2020046

[18]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033

[19]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016

[20]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

 Impact Factor: 

Metrics

  • PDF downloads (97)
  • HTML views (937)
  • Cited by (0)

Other articles
by authors

[Back to Top]