关键词: 强罗马控制数, 特殊图, 完全二部图, 完全图的刺图

Abstract: The determination of the domination number of a graph is a NP-complete problem. It is of great theoretical significance to investigate the exact values or better upper and lower bounds of the domination number of a graph. Strong Roman domination number, which is an important kind of domination number, not only is widely applied in protein structure research, circuit diagram design and computer programming, but also has prominent applications in scientific fields such as logic, linguistics, communication network and artificial intelligence. In this paper, the methods of mathematical induction and classification discussion are mainly used to deeply investigate the relationship between the strong Roman domination number and the order of a graph. We show that the strong Roman domination number of some special graphs such as windmill graph, complete bipartite graph, and thorn graph of complete graph is not greater than the six sevenths of the order of the graph.

Key words: strong Roman domination number, special graphs, complete bipartite graphs, thorn graph of complete graphs