
The paper studies the Roman domination in graphs. It is a special kind of domination whose introduction was motivated by military rules of the ancient Roman Empire. Let \(G\) be a graph with vertex set \(V(G)\), and let \(f: V(G)\to \{0,1,2\}\). If to each vertex \(v\) with \(f(v)= 0\) there exists a vertex \(w\) with \(f(w)= 2\) adjacent to \(v\), then \(f\) is called a Roman dominating function on \(G\). Its weight is \(w(f)= \sum_{x\in V(G)}f(x)\). The minimum weight of a Roman dominating function on \(G\) is the Roman domination number \(\gamma_R(G)\) of \(G\). Properties of Roman dominating functions on \(G\) are described and some bounds for \(\gamma_R(G)\) are found. For some types of graphs, including paths and cycles, exact values are found. Special attention is paid to graphs \(G\) with \(\gamma_R(G)\leq \gamma(G)+ 2\), where \(\gamma(G)\) is the well-known domination number of \(G\). Graphs with \(\gamma_R(G)= 2\gamma(G)\) are called Roman graphs and are studied. At the end of the paper open problems are suggested.
Extremal problems in graph theory, Roman graphs, Domination, Theoretical Computer Science, Graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), facilities, Facilities location, Discrete Mathematics and Combinatorics, Roman dominating function, Roman domination number
Extremal problems in graph theory, Roman graphs, Domination, Theoretical Computer Science, Graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), facilities, Facilities location, Discrete Mathematics and Combinatorics, Roman dominating function, Roman domination number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 366 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 0.1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 0.1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
