Roman domination in graphs. (Q1427467)

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.