Research On Modern Roman Domination Problem Of Graphs

Graph theory,as a part of mathematics,uses graphs as the basic objects of study,with vertices representing certain objects and edges representing specific relationships between two objects.Graph theory is widely used in many fields such as computer science,complexity theory,statistics,and theoretical analysis of computer-related interdisciplinary subjects.Graph theory has also gradually evolved into various academic branches,such as algebraic graph theory,topological graph theory,combinatorial optimization,complexity theory,and so on,providing a solid theoretical foundation for scientific and technological progress and understanding of the world.The concept of a domination set,defined as a set of vertices in a graph such that every other vertex in the graph is adjacent to a vertex in the domination set,is an important concept in graph theory.Domination problems,such as locating problems and the Roman domination problem in defending the Roman Empire,are widely used in combinatorial optimization problems.After continuous research by predecessors,many variants of the domination problem have been derived to deal with various problems,such as double Roman domination,Roman domination,modern Roman domination,three Roman domination,edge domination,symbolic edge domination,and so on.Future generations have added additional conditions and restrictions to the research on Roman domination set by predecessors to derive new variants of domination problems,such as complete Roman domination set and symbolic Roman domination set.This theme mainly studies the modern Roman domination theory,mainly from the perspectives of the properties,upper and lower bounds,relationships with other Roman-type dominations,computational complexity,algorithm design,and analysis of the modern Roman domination set,and the specific contents are as follows:1.Expand and summarize the research results on the special properties of the modern Roman domination set on the graph and give a characterization of the lower bound of the modern Roman domination number for a general graph,and prove that the lower bound is attainable.2.Characterize the upper and lower bounds of the modern Roman domination set on tree graphs,and prove that both the upper and lower bounds are achievable.3.Study the relationship between the modern Roman domination set and the Roman domination set on special graphs,and the relationship between the modern Roman domination set and the standard domination set.4.Study the computational complexity theory,design and characterization of the modern Roman domination problem,and prove the NP completeness of the modern Roman domination set problem on chordal graphs and bipartite graphs.5.Use dynamic programming to study and design a linear time algorithm for solving the modern Roman domination tree on a tree.