Theory On Roman Domination In Graphs

Graph theory is a branch of discrete mathematics,takin Ggraph as the main research object,studying the relationship between vertices.It has profound research in the field of theoretical computing and has extensive research in many cross fields such as operations research,bioinformatics,artificial intelligence,and so on.The dominating set problem is one of the core problems in graph theory,which is applied in many fields of research such as Computer Science and Operational Research.It is a kind of combinatorial optimization problem widely used.The dominating set problem is that function1)performs assignment operations on all vertices of graphaccording to some restrictions,and the minimum assignment sum of graphis solved.According to different conditions or restrictions,the dominating set problem has all kinds of varieties,such as total domination problem,Roman domination problem,Roman{k}domination problem,signed domination problem,independent domination problem,and so on.The new variants of Domination problem can be superimposed from different conditions and restrictions such as total Roman domination problem,independent domination,and so on.This paper mainly studies the computational complexity and algorithm design and analysis of a series of variant Roman control sets,including:1.Summarize and extend the NP complete of Roman{3}domination,prove that Roman{3}domination are NP complete on planar graph and chord bipartite graph.2.Solve two open problems for total Roman 3 domination,prove that Roman{3}domination is NP complete on planar graph and chord bipartite graph,and present a linear time algorithm in any tree for total Roman{3}domination.3.Summarize and extend the NP complete of independent Roman domination,and present an exact algorithm for independent Roman domination with time complexity O(1.5671~?).