QA553 : On the perfect Roman domination number in some classes of graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2019
  Authors:
Abstarct: A perfect Roman dominating function on a graph G is a function  f: V → {0,1,2} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weght of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted  γ_R^P (G), is the minimum weigh of a perfect Roman dominating function in G. In this thesis, we study this parameter and present some new bounds for it. Then, we show that the PERFECT ROM-DOM problem is NP-complete, even when restricted to bipartite graphs. Also, we will improve some of previous given bounds and especially we present a new upper bound for the class of trees. Moreover, we characterize the class of perfect Roman domination edge critical trees. Finally, we provide a constructive characterization of the trees for which the perfect Roman domination number strongly equals the weak Roman domination number.
  Keywords:
 #Domination number    #Roman domination number    #perfect Roman domination number    #Weak  Roman domination number    #Graph    #Tree   Link
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: