NP-completeness of some generalized hop and step domination parameters in graphs

Document Type : Original paper

Authors

1 Islamic Azad University

2 Shahed University

Abstract

‎Let $r\geq 2$. A subset $S$ of vertices of a graph $G$ is a $r$-hop independent dominating set if every vertex outside $S$ is at distance $r$ from a vertex of $S$, and for any pair $v, w\in S$, $d(v, w)\neq r$. A $r$-hop Roman dominating function ($r$HRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v \in V$ with $f(v) = 0$ there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$-step Roman dominating function ($r$SRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v$ with $f(v)=0$ or $2$, there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$HRDF $f$ is a $r$-hop Roman independent dominating function if for any pair $v, w$ with non-zero labels under $f$, $d(v, w)\neq r$. We show that the decision problem associated with each of $r$-hop independent domination, $r$-hop Roman domination, $r$-hop Roman independent domination and $r$-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Keywords

Main Subjects

References

[1] S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan, and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proceedings Math. Sci. 125 (2015), 449–455.
https://doi.org/10.1007/s12044-015-0251-6
[2] S.K. Ayyaswamy, C. Natarajan, and Y.B. Venkatakrishnan, Hop domination in graphs, Manuscript (2015).
[3] Y. Caro, A. Lev, and Y. Roditty, Some results in step domination of graphs, Ars Combin. 68 (2003), 105–114.
[4] G. Chartrand, F. Harary, M. Hossain, and K. Schultz, Exact 2-step domination in graphs, Math. Bohem. 120 (1995), no. 2, 125–134.
http://doi.org/10.21136/MB.1995.126228
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, p. 365–409.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Comb. Comput. 115 (2020), 141–171.
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE J. Graphs Combin. 17 (2020), no. 3, 966–984.
https://doi.org/10.1016/j.akcej.2019.12.001
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, p. 273–307.
[9] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
https://doi.org/10.1016/j.disc.2003.06.004
[10] G. Dror, A. Lev, and Y. Roditty, A note: some results in step domination of trees, Discrete Math. 289 (2004), no. 1-3, 137–144.
https://doi.org/10.1016/j.disc.2004.08.007
[11] T.W. Haynes, S.T. Hedetniemi, and P.J. Salter, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[12] M.A. Henning and N. Jafati Rad, On 2-step and hop dominating sets in graphs, Graphs Combin. 33 (2017), 913–927.
https://doi.org/10.1007/s00373-017-1789-0
[13] P. Hersh, On exact n-step domination, Discrete Math. 205 (1999), no. 1-3, 235–239.
https://doi.org/10.1016/S0012-365X(99)00024-2
[14] N. Jafari Rad and A. Poureidi, On hop Roman domination in trees, Commun. Comb. Optim. 4, no. 2, 201–208.
https://doi.org/10.22049/cco.2019.26469.1116
[15] N. Jafari Rad and E. Shabani, On the complexity of some hop domination parameters, Electron. J. Graph Theory Appl. 7 (2019), no. 1, 77–89.
https://doi.org/10.5614/ejgta.2019.7.1.6
[16] M.F. Jalalvand and N. Jafari Rad, On the complexity of $k$-step and $k$-hop dominating sets in graphs, Math. Montisnigri 40 (2017), 36–41.
[17] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, Freeman, 1979.
[18] R.M. Karp, Reducibility Among Combinatorial Problems, Springer, 2010.
[19] C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, An. Stt. Univ. Ovidius Constanta 23 (2015), no. 2, 187–199.
https://doi.org/10.1515/auom-2015-0036
[20] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
https://doi.org/10.1080/00029890.2000.12005243
[21] E. Shabani, N. Jafari Rad, and A. Poureidi, Graphs with large hop Roman domination number, Computer Sci. J. Moldova 79 (2019), no. 1, 3–22.
[22] E. Shabani, N. Jafari Rad, A. Poureidi, and A. Alhevaz, Hop Roman domination in graphs, Ars Combin. (to appear).
[23] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[24] Y. Zhao, L. Miao, and Z. Liao, A linear-time algorithm for 2-step domination in block graphs, J. Math. Res. Appl. 35 (2015), no. 3, 136–138.
http://doi.org/10.3770/j.issn:2095-2651.2015.03.006
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 October 2023

Files

Share

How to cite

Statistics