Mixed domination and 2-independence in trees

Chang Wan; Zehui Shao; Nasrin Dehgardi; Rana Khoeilar; Marzieh Soroudi; Asfand Fahad; Chang Wan; Zehui Shao; Nasrin Dehgardi; Rana Khoeilar; Marzieh Soroudi; Asfand Fahad

doi:10.3934/math.2020357

AIMS Mathematics

2020, Volume 5, Issue 6: 5564-5571. doi: 10.3934/math.2020357

Previous Article Next Article

Research article Special Issues

Mixed domination and 2-independence in trees

1.
Guangdong Polytechnic of Science and Technology, Guangzhou 510640, China
2.
Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
3.
Department of Mathematics and Computer Science, Sirjan University of Technology, Sirjan, I. R. Iran
4.
Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran
5.
Department of Mathematics, COMSATS University Islamabad, Vehari Campus, Vehari 61100, Pakistan

Received: 27 April 2020 Accepted: 23 June 2020 Published: 01 July 2020
MSC : 05C05, 05C69

We investigate some relationships between two vastly studied parameters of a simple graph $G$. These parameters include mixed domination number (denoted by $\gamma_m(G)$) and 2-independence number ($\beta_2(G)$). For a tree $T$, we obtain $\frac{3}{4}\beta_2(T)\ge \gamma_m(T)$ and characterized all those trees which attain the equality.
- mixed dominating function,
- mixed domination number,
- 2-independent set,
- 2-independence number
Citation: Chang Wan, Zehui Shao, Nasrin Dehgardi, Rana Khoeilar, Marzieh Soroudi, Asfand Fahad. Mixed domination and 2-independence in trees[J]. AIMS Mathematics, 2020, 5(6): 5564-5571. doi: 10.3934/math.2020357

Related Papers:

Abstract

We investigate some relationships between two vastly studied parameters of a simple graph $G$. These parameters include mixed domination number (denoted by $\gamma_m(G)$) and 2-independence number ($\beta_2(G)$). For a tree $T$, we obtain $\frac{3}{4}\beta_2(T)\ge \gamma_m(T)$ and characterized all those trees which attain the equality.

References

[1]	J. Amjadi, M. Valinavaz, Relating total double Roman domination to 2-independence in trees, Acta Math. Univ. Comenianae, 2020, 1-9.
[2]	Y. Alavi, M. Behzad, L. Lesniak, et al. Total matchings and total coverings of graphs, J. Graph Theor., 1 (1977), 135-140. doi: 10.1002/jgt.3190010209
[3]	Y. Alavi, J. Q. Liu, J. F. Wang, et al. On total covers of graphs, Discrete Math., 100 (1992), 229-233. doi: 10.1016/0012-365X(92)90643-T
[4]	J. Amjadi, S. M. Sheikholeslami, M. Valinavaz, et al. Independent Roman domination and 2- independence in trees, Discrete Mathematics, Algorithms and Applications, 10 (2018), 1850052.
[5]	N. Dehgardi, S. M. Sheikholeslami, M. Valinavaz, et al. Domination number, independent domination number and 2-independence number in trees, Discuss. Math. Graph T., 2018, 1-11.
[6]	Y. Caro, A. Hansberg, New approach to the k-independence number of a graph, Electron. J. Comb., 20 (2013), 1-17.
[7]	Y. Caro, Z. Tuza, Improved lower bounds on k-independence, J. Graph Theor., 15 (1991), 99-107. doi: 10.1002/jgt.3190150110
[8]	M. Chellali, O. Favaron, A. Hansberg, et al. k-domination and k-independence in graphs: A survey, Graph. Combinator., 28 (2012), 1-55.
[9]	M. Chellali, N. Meddah, Trees with equal 2-domination and 2-independence numbers, Discuss. Math. Graph T., 32 (2012), 263-270. doi: 10.7151/dmgt.1603
[10]	N. Dehgardi, Mixed Roman domination and 2-independence in trees, Communications in Combinatorics and Optimization, 3 (2018), 79-91.
[11]	O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory, B, 39 (1985), 101-102. doi: 10.1016/0095-8956(85)90040-1
[12]	J. F. Fink, M. S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, In: Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, Inc., 1985, 301-311.
[13]	S. Kogan, New results on k-independence of graphs, Electron. J. Comb., 24 (2017), 2-15.
[14]	P. Hatami, An approximation algorithm for the total covering problem, Discuss. Math. Graph Theory, 27 (2007), 553-558. doi: 10.7151/dmgt.1380
[15]	J. K. Lan, G. J. Chang, On the mixed domination problem in graphs, Theor. Comput. Sci., 467 (2013), 84-93.
[16]	N. Meddah, M. Chellali, Roman domination and 2-independence in trees, Discrete Mathematics, Algorithms and Applications, 9 (2017), 1-6.
[17]	D. F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math., 91 (1999), 155-175. doi: 10.1016/S0166-218X(98)00147-4
[18]	E. Nordhaus, Generalizations of graphical parameters, in: Theory and Applications of Graphs, 1978.
[19]	D. B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, (2001).
[20]	Y. Zhao, L. Kang, M. Y. Sohn, The algorithmic complexity of mixed domination in graphs, Theor. Comput. Sci., 412 (2011), 2387-2392. doi: 10.1016/j.tcs.2011.01.029
[21]	E. Zhu, C. Liu, On the semitotal domination number of line graphs, Discrete Appl. Math., 254 (2019), 295-298. doi: 10.1016/j.dam.2018.06.010
[22]	E. Zhu, C. Liu, F. Deng, et al. On upper total domination versus upper domination in graphs, Graph. Combinator., 35 (2019), 767-778. doi: 10.1007/s00373-019-02029-y
[23]	E. Zhu, Z. Shao, J. Xu, Semitotal domination in claw-free cubic graphs, Graph. Combinator., 33 (2017), 1119-1130. doi: 10.1007/s00373-017-1826-z

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)