Research article

Complexity of signed total $k$-Roman domination problem in graphs

  • Received: 02 July 2020 Accepted: 27 October 2020 Published: 05 November 2020
  • MSC : 05C69

  • Let $G$ be a simple graph with finite vertex set $V(G)$ and $S = \{-1, 1, 2\}$. A signed total Roman $k$-dominating function (STRkDF) on a graph $G$ is a function $f:V(G)\to S$ such that (i) any vertex $y$ with $f(y) = -1$ is adjacent to at least one vertex $t$ with $f(t) = 2, $ (ii) $\sum_{t\in N(y)}f(t)\geq k$ holds for any vertex $y$. The $weight$ of an STRkDF $f$, denoted by $\omega(f)$, is $\sum_{y\in V(G)}f(y)$, and the minimum weight of an STRkDF is the signed total Roman k-domination number, $\gamma_{stR}^k(G), $ of $G$. In this article, we prove that the decision problem for the signed total Roman $k$-domination is NP-complete on bipartite and chordal graphs for $k\in\{1, 2\}$.

    Citation: Saeed Kosari, Yongsheng Rao, Zehui Shao, Jafar Amjadi, Rana Khoeilar. Complexity of signed total $k$-Roman domination problem in graphs[J]. AIMS Mathematics, 2021, 6(1): 952-961. doi: 10.3934/math.2021057

    Related Papers:

  • Let $G$ be a simple graph with finite vertex set $V(G)$ and $S = \{-1, 1, 2\}$. A signed total Roman $k$-dominating function (STRkDF) on a graph $G$ is a function $f:V(G)\to S$ such that (i) any vertex $y$ with $f(y) = -1$ is adjacent to at least one vertex $t$ with $f(t) = 2, $ (ii) $\sum_{t\in N(y)}f(t)\geq k$ holds for any vertex $y$. The $weight$ of an STRkDF $f$, denoted by $\omega(f)$, is $\sum_{y\in V(G)}f(y)$, and the minimum weight of an STRkDF is the signed total Roman k-domination number, $\gamma_{stR}^k(G), $ of $G$. In this article, we prove that the decision problem for the signed total Roman $k$-domination is NP-complete on bipartite and chordal graphs for $k\in\{1, 2\}$.


    加载中


    [1] H. Abdollahzadeh Ahangar, M. Chellali, S. M. Sheikholeslami, Signed double Roman domination in graphs, Discrete Appl. Math., 257 (2019), 1-11. doi: 10.1016/j.dam.2018.09.009
    [2] H. Abdollahzadeh Ahangar, R. Khoeilar, L. Shahbazi, S. M. Sheikholeslami, Signed total double Roman domination, Ars Combin., (to appear).
    [3] H. Abdollahzadeh Ahangar, R. Khoeilar, L. Shahbazi, S. M. Sheikholeslami, Bounds on signed total double Roman domination, Commun. Comb. Optim., 5 (2020), 191-206.
    [4] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Roman domination in graphs. In: Topics in Domination in Graphs, (Eds), T. W. Haynes, S. T.Hedetniemi, M. A. Henning, Springer Nature Switzerland AG, 2020.
    [5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination. In: Structures of Domination in Graphs, (Eds), T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Springer Nature Switzerland AG, 2020.
    [6] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb., in press.
    [7] M. Chellai, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory, in press.
    [8] M. Chellai, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput., (to appear).
    [9] N. Dehgardi, L. Volkmann, Signed total Roman k-domination in directed graphs, Commun. Comb. Optim., 1 (2016), 165-178.
    [10] G. Hickey, F. Dehne, A. Rau-Chaplin, C. Blouin, SPR distance computation for unrooted trees, Evolutionary Bioinformics Online, 4 (2008), 17-27.
    [11] R. Khoeilar, L. Shahbazi, S. M. Sheikholeslami, Z. Shao, Bounds on the signed total Roman 2-domination in graphs, Discrete Math. Algorithms Appl., 12 (2020), 2050013. doi: 10.1142/S1793830920500135
    [12] L. Volkmann, Signed total Roman domination in graphs, J. Comb. Optim., 32 (2016), 855-871. doi: 10.1007/s10878-015-9906-6
    [13] L. Volkmann, On the signed total Roman domination and domatic numbers of graphs, Discrete Appl. Math., 214 (2016), 179-186. doi: 10.1016/j.dam.2016.06.006
    [14] L. Volkmann, Signed total Roman k-domination in graphs, J. Combin. Math. Combin. Comput., 105 (2018), 105-116.
  • Reader Comments
  • © 2021 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(3001) PDF downloads(119) Cited by(0)

Article outline

Figures and Tables

Figures(8)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog