Some results on roman domination edge critical graphs (Q1927700)

If \(G\) is a graph, then a function \(V(G)\rightarrow \{0,1,2\}\) is a Roman dominating function if any vertex \(u\) with \(f(u)=0\) has a neighbor \(v\) with \(f(v)=2\). The Roman domination number \(\gamma_{R}(G)\) is the minumum weight of a Roman dominating function. A graph \(G\) is \(\gamma_{R}\)-edge critical if \(\gamma_{R}(G+e) < \gamma_{R}(G)\) holds for any edge \(e \notin E(G)\). In this paper, several structural properties of \(\gamma_{R}\)-edge critical graphs are proved. Removing a vertex from such a graph never increases the Roman dominating number, while vertices whose removal does not change the invariant induce a complete subgraph. The order of an \(\gamma_{R}\)-edge critical graphs is at most, roughly speaking, \(\gamma_{R} \Delta(G) /2\). The following classes of graphs are characterized: 2-\(\gamma_{R}\)-edge critical graphs, 3-\(\gamma_{R}\)-edge critical graphs, \(n\)-\(\gamma_{R}\)-edge critical graphs of order \(n\), and \((n-1)\)-\(\gamma_{R}\)-edge critical graphs of order \(n\). The diameter of \(\gamma_{R}\)-edge critical graphs is bounded. For any \(n\geq 6\), an \(n\)-\(\gamma_{R}\)-edge critical graph with diameter 5 is constructed.