| Graph theory is a discipline that studies graph models composed of vertex sets and edge sets.It is widely used in computer networks,communication networks,circuit design,and cryptography,among other fields.It provides a solid theoretical foundation for modern scientific progress and our understanding of the world.The dominating set is an important concept in graph theory,defined as a set of vertexes in a graph where any other vertex in the graph is adjacent to at least one vertex in the set.The dominating set problem originates from real-life location problems and has gradually led to more valuable variant problems as scientific progress advances.For example,the Roman domination problem arises from the need to defend the entire Roman Empire with the least number of soldiers,while the independent domination problem is derived from the queen placement problem in chess.The independent Roman domination problem studied in this paper combines the Roman domination problem with the independent domination problem.Its objective is to find a vertex set in a graph that satisfies both independence and Roman properties,selecting the one with the minimum weight among all satisfying vertex sets.This paper primarily focuses on the complexity,algorithm design,and analysis of the independent Roman domination problem.The specific contents are as follows:1.Summarizing existing research results on the independent Roman domination problem and proving that the problem is NP-complete on bipartite graphs.2.Constructing two special types of graphs: GR graphs and GIR graphs,and studying the complexity differences between the independent Roman domination problem and the Roman domination problem on these two special graph types.3.Designing linear time solvable algorithms for the independent Roman domination problem on arbitrary trees and threshold graphs,and proving their correctness. |
