QA553 : On the perfect Roman domination number in some classes of graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2019
Authors:
Mahsa Darkooti [Author], Sadegh Rahimi Shearbaf Moghaddas[Supervisor], Abdollah Alhevaz[Supervisor], Hadi Rahbani [Advisor]
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: