Criticality indices of Roman domination of paths and cycles (Q2848727)

For a graph \(G=(V,E)\), a Roman dominating function on \(G\) is a function \(f: V(G)\rightarrow \{0,1,2\}\) such that every vertex \(u\) for which \(f(u)=0\) is adjacent to at least one vertex \(v\) with \(f(v)=2\). The weight of a Roman dominating function is defined as \(f(V(G))=\sum_{u\in V(G)}f(u)\). The minimum weight of a Roman dominating function on a graph \(G\) is called the Roman domination number of \(G\), denoted by \(\gamma_R(G)\). The removal criticality index of a graph \(G\) is defined as \(\mathrm{ci}^-_R(G)=(\sum_{e\in E(G)}(\gamma_R(G)-\gamma_R(G-e))/|E(G)|\) and the adding criticality index of \(G\) is defined as \(\mathrm{ci}^+_R(G)=(\sum_{e\in E(\overline{G})}(\gamma_R(G)-\gamma_R(G+e))/|E(\overline{G})|\) where \(\overline{G}\) means the complement of \(G\). For \(n\geq 3\), let \(P_n, C_n\) be a path and a cycle of order \(n\), respectively.NEWLINENEWLINEIn this paper, the authors determine the values of \(\mathrm{ci}^-_R(P_n),\mathrm{ci}^+_R(C_n),\mathrm{ci}^+_R(P_n)\).