|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|