|
On the Strong Roman Domination Number of Some Special Graphs
XU Jia-xue, WANG Zhi-ping
2020, 37 (3):
295-302.
doi: 10.3969/j.issn.1005-3085.2020.03.004
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.
Related Articles |
Metrics
|