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

被引:0
作者
Asemian, Ghazaleh [1 ]
Rad, Nader Jafari [2 ]
Tehranian, Abolfazl [1 ]
Rasouli, Hamid [1 ]
机构
[1] Islamic Azad Univ, Dept Math, Sci & Res Branch, Tehran, Iran
[2] Shahed Univ, Dept Math, Tehran, Iran
关键词
Dominating set; Hop dominating set; Step dominating set; Hop Inde-pendent set; Hop Roman dominating function; Hop Roman independent dominating function; Complexity; COMPLEXITY;
D O I
10.22049/CCO.2023.28699.1676
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let r >= 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 is an element of S, d(v, w) =6 r. A r-hop Roman dominating function (rHRDF) is a function f on V (G) with values 0,1 and 2 having the property that for every vertex v is an element of 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 (rSRDF) 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 rHRDF f is a r-hop Roman independent dominating function if for any pair v, w with non-zero labels under f, d(v, w) =6 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.
引用
收藏
页码:181 / 193
页数:13
相关论文
共 25 条
[1]   Hop total Roman domination in graphs [J].
Abdollahzadeh Ahangar, H. ;
Chellali, M. ;
Sheikholeslami, S. M. ;
Soroudi, M. .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2023, 20 (01) :73-78
[2]   Bounds on the hop domination number of a tree [J].
Ayyaswamy, S. K. ;
Krishnakumari, B. ;
Natarajan, C. ;
Venkatakrishnan, Y. B. .
PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2015, 125 (04) :449-455
[3]  
Ayyaswamy S.K., 2015, HOP DOMINATION UNPUB
[4]  
Caro Y, 2003, ARS COMBINATORIA, V68, P105
[5]  
Chartrand G., 1995, MATH BOHEM, V120, P125, DOI [10.21136/MB.1995.126228, DOI 10.21136/MB.1995.126228]
[6]  
Chellai M., 2020, J COMBIN MATH COMB C, V115, P141
[7]   Varieties of Roman domination II [J].
Chellali, M. ;
Jafari Rad, N. ;
Sheikholeslami, S. M. ;
Volkmann, L. .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) :966-984
[8]  
Chellali M., 2020, Topics in Domination in Graphs, P365
[9]   Roman domination in graphs [J].
Cockayne, EJ ;
Dreyer, PA ;
Hedetniemi, SM ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2004, 278 (1-3) :11-22
[10]   A note: some results in step domination of trees [J].
Dror, G ;
Lev, A ;
Roditty, Y .
DISCRETE MATHEMATICS, 2004, 289 (1-3) :137-144