QA587 : Some functional versions of hop domination‎ in graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2020
Authors:
Elaheh‎ Shabani [Author], Nader Gafary rad[Supervisor]
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)=_vV 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,wV_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: