QA587 : Some functional versions of hop domination in graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2020
Authors:
Abstarct: A subset S of vertices of a graph G is a hop dominating set (HDS) if every vertex outside S is at
distance two from a vertex of S. A subset S of vertices of a graph G is a hop independent dominating set if S is a HDS and for any pair v, w S, d(v, w)≠2. The hop domination number of G ,_h (G), is the minimum cardinality of a hop dominating set of G .The hop independent domination number of G is the minimum cardinality of a hop independent dominating set of G. A hop Roman dominating function (HRDF) is a function f:V(G)⟼{0,1,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)=2. The weight of a HRDF f is the sum f(V)=_vV f(v). The minimum weight of a HRDF on G is called the hop Roman domination number of G and is denoted by _hR (G). For a HRDF f in a graph G, we denote by V_i^f the set of all vertices of G with label i under f.
Thus a HRDF f can be represented by a triple (V_0^f,V_1^f,V_2^f). A HRDF f=(V_0^f,V_1^f,V_2^f) is a hop Roman independent dominating function (HRIDF) if for any pairv,wV_1^f V_2^f , d(v, w)≠2. In this thesis, we study the complexity of hop independent dominating problem, the hop Roman domination function problem and hop Roman independent domination function problem, and show that decision problem for each of the above three problems is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs. Also, we characterize all graphs G of order n with ا_hR (G)=n or ا_hR (G)=n-1. Finally, we characterize all trees T for which
_hR (T)=_h (T)+1
or
_hR (T)=_h (T)+2
Keywords:
#hop dominating set #hop Roman dominating function #graph #tree. Keeping place: Central Library of Shahrood University
Visitor:
Visitor: