Research article Special Issues

Mixed domination and 2-independence in trees

  • 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.

    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:

  • 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.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2836) PDF downloads(305) Cited by(3)

Article outline

Figures and Tables

Figures(2)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog