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

Saeed Kosari; Yongsheng Rao; Zehui Shao; Jafar Amjadi; Rana Khoeilar; Saeed Kosari; Yongsheng Rao; Zehui Shao; Jafar Amjadi; Rana Khoeilar

doi:10.3934/math.2021057

AIMS Mathematics

2021, Volume 6, Issue 1: 952-961. doi: 10.3934/math.2021057

Previous Article Next Article

Research article

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

1.
Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
2.
Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz 51368, I. R. Iran

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\}$.
- signed total Roman $k$-dominating function,
- signed total Roman $k$-domination number,
- complexity
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:

Abstract

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\}$.

References

[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

Your name:*

Email:*
© 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)