>
Fa   |   Ar   |   En
   np-completeness of some generalized hop and step domination parameters in graphs  
   
نویسنده asemian ghazale ,jafari rad nader ,tehranian abolfazl ,rasouli hamid
منبع communications in combinatorics and optimization - 2025 - دوره : 10 - شماره : 1 - صفحه:181 -193
چکیده    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 ∈ s, d(v, w) ≠ 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 ∈ 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) ≠ 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.
کلیدواژه dominating set ,hop dominating set ,step dominating set ,hop independent set ,hop roman dominating function ,hop roman independent dominating function ,complexity
آدرس islamic azad university, tehran science and research branch, department of mathematics, iran, shahed university, department of mathematics, iran, islamic azad university, tehran science and research branch, department of mathematics, iran, islamic azad university, tehran science and research branch, department of mathematics, iran
پست الکترونیکی hrasouli@srbiau.ac.ir
 
     
   
Authors
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved