Research On Roman Class Domination Theory Of Graph

Graph theory is an important part of discrete mathematics.With the advancement of computer technology,graph theory has developed rapidly both in theoretical research and practical application,and played an important role in computer science,statistics,bioinformatics and other disciplines.The domination theory in graph originated in the middle of the 20th century is an import research direction in graph theory.The domination problem is to assign the vertices in the graph according to the rules of the domination function,and solve the minimum weight of domination function.The research directions of domination theory includes:the upper and lower bounds of domination number,domination number of special graphs,computation complexity,algorithm analysis.There have been many variants of the domination depending on different domination functions,such as total domination,signed domination,edge domination,Roman domination and so on.This paper mainly studies the Roman domination class.Firstly,we introduce the research background and terminology of domination in the introduction part,and also introduce the NP-completeness theory which is closely related to domination in graph.In the second chapter,we study the Roman{3}domination of graph and give its domination number on the grid graph P₂□P_m,and we also characterize the treethat satisfies γ_{R3}（T） = |V（T）|.In the third chapter,we study the NP-completeness of Roman domination class.We prove respectively the NP-completeness of perfect Roman{2}domination on chordal graph and the NP-completeness of perfect double Roman domination on bipartite graph.In the fourth chapter,we extend the concept of"perfect"to Roman{3}domination.We propose the perfect Roman{3}domination and give an upper bound of perfect Roman{3}domination number on the tree.