An Upper Bound on the Total Roman \(\{2\}\)-domination Number of Graphs with Minimum Degree Two

1. Introduction

In this paper, \({G}\) is a simple graph with vertex set \(V=V({G})\) and edge set \(E=E({G})\). The order \(|V|\) of \({G}\) is denoted by \(n({G})\). For every vertex \({v}\in V\), the open neighborhood \(N(v)\) is the set \(\{{u}\in V({G})\mid {vu}\in E({G})\}\) and the closed neighborhood of \({v}\) is the set \(N[{v}]=N({v})\cup\{{v}\}\). The degree of a vertex \({v}\in V\) is \(\deg_{{G}}({v})=|N({v})|\). The minimum and maximum degree of a graph \({G}\) are denoted by \(\delta({G})\) and \(\Delta({G})\), respectively. Let \(P_{n}\) and \(C_{n}\) be the path and cycle of order \(n\).

For a graph \({G}\) and a positive integer \(k\), let \(f:V({G})\rightarrow \{0,1,2,\ldots,k\}\) be a function, and let \((V_{0},V_{1},V_{2},\ldots,V_{k})\) be the ordered partition of \(V({G})\) induced by \(f\), where \(V_{i}=\{{v}\in V\mid f({v})=i\}\) for \(i\in\{0,1,\ldots,k\}\). There is a \(1\)–\(1\) correspondence between the function \(f:V\rightarrow\{0,1,2,\dots,k\}\) and the ordered partitions \((V_{0},V_{1},V_{2},\ldots,V_{k})\) of \(V\), so we will write \(f=(V_{0},V_{1},V_{2},\ldots,V_{k})\). The weight of \(f\) is the value \(f(V({G}))=\sum_{{u}\in V({G})}f({u}).\)

In [1], Chellali et al. investigated the Roman \(\{2\}\)-domination (called in [2] and elsewhere Italian domination) defined as follows: a Roman \(\{2\}\)-dominating function (R\(\{2\}\)-DF) on \(G\) is a function \(f=(V_{0},V_{1},V_{2})\) with the property that for every vertex \({v}\in V_{0}\) there is a vertex \({u}\in N({v})\), with \({u}\in V_{2}\) or there are two vertices \(x,y\in N({v})\) with \(x,y\in V_{1}\). The Roman \(\{2\}\) -domination number \(\gamma_{{R2}}({G})\) is the minimum weight of an R\(\{2\}\)-DF on \({G}\). Some variant of Italian domination has been studied for example in [3, 4]. Note that, Roman domination and its variants have many applications in the areas such as facility location problems, planning of defence strategies and surveillance related problems, etc. The literature on this topic has been detailed in several papers [5, 6, 7, 8, 9, 10].

A total Roman \(\{2\}\)-dominating function (total Roman \(\{2\}\)-dominating function) is an R\(\{2\}\)-DF \(f\) such that the set of vertices with \(f({v})>0\) induces a subgraph with no isolated vertices. The weight of a total Roman \(\{2\}\)-dominating function is the sum of its function values over all vertices, and the minimum weight of a total Roman \(\{2\}\)-dominating function of \({G}\) is the total Roman \(\{2\}\)-domination number \(\gamma_{tR2}({G})\). Total Roman \(\{2\}\)-domination was first studied in [11] and investigated in [12, 13].

It is observed in [11] that for all connected graphs \(G\) of order \(n\) with \(\delta(G) \ge 1\), \(2 \le \gamma_{tR2}({G})\le n\) and the graphs attaining the bounds are characterized.

In this paper, we prove that for every graph \(G\) of order \(n\) with minimum degree at least two, \(\gamma_{tR2}({G})\leq \frac{5n}{6}\).

The proof of the following results can be found in [].

2. A Preliminary Result

Here we focus to construct an upper bound for the total Roman \(\{2\}\)– domination number of connected graphs with minimum degree at least two. We first make a result as follows.

For positive integers \(j\ge 3\) and \(l\ge 1\), let the graph \(C_{j,l}\) be obtained from a cycle \(C_j=x_1x_2\ldots x_jx_1\) by adding a pendant path \(x_1y_1y_2\ldots y_l\).

Let \({\mathcal{R}}_1\) be the family of all connected loopless multigraphs with minimum degree at least three and let \({\mathcal{R}}\) be the family of all graphs constructed by some graph in \({\mathcal{R}}_1\) by subdividing whole edges \(t\) times with \(1\le t\le 5\). We observe that any graph in \({\mathcal{R}}\) has order at least 5.

Proof. Let \({G}\in {\mathcal{R}}\) be a graph of order \(n\). We continue the proof by induction on \(n\). If \(n=5\), then \({G}\) is isomorphic to \(K_{2,3}\) and clearly the result holds. Assume that \(n\ge 6\) and let the result hold for any graph of \({\mathcal{R}}\) of order smaller than \(n\). Let \({G}\in {\mathcal{R}}\) be a graph of order \(n\ge 6\). Let \(M=\{{u}\in V({G})\mid \deg_G({u})\ge 3\}\) and let \(N=V({G})-M\). By definition we have \(|M|\ge 2\). An \(M\)-ear path in \({G}\) is a path \(W\) of \({G}\) so that \(V(W)\subseteq N\) and the endvertices of \(W\) are adjacent to vertices of \(M\). For each \(i\ge 1\), define \(\mathcal{W}_i=\{W\mid W\) is an \(M\)-ear path with \(|V(W)|=i\}\). Let \(\mathcal{W}=\bigcup_{i\ge 1}\mathcal{W}_i\). Observe that \(M\cup \bigcup_{W\in \mathcal{W}}V(W)\) is a partition of \(V({G})\). For each \(M\)-ear path \(W\in \mathcal{W}\), let \(X_W=\{w\in M\mid w\) is adjacent to a leaf of \(W\}\). Clearly \(M=\bigcup_{W\in \mathcal{W}}X_W\) and \(|X_W|=2\) for each \(W\in \mathcal{W}\). First let there exist an \(M\)-ear path \(W=x_1x_2\ldots x_{k}\in \mathcal{W}_{4} \cup \mathcal{W}_{5}\) and \(X_W=\{t_1,t_2\}\) so that \(t_1x_1,t_2x_{k}\in E({G})\). Assume that the graph \({G}'\) is obtained from \({G}\) by removing \(x_2,\ldots,x_k\) and adding the edge \(x_1t_2\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) such that \(f(t_1), f(t_2)\ge 1\) and \(\omega(f)\le \frac{5(n-k+1)}{6}\). If \(f(x_1)\ge 1\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_2)=0, g(x_3)={g(x_4)=}\ldots=g(x_k)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. If \(f(x_1)=0\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_4)=0, g(x_i)=1\) for \(i\in \{2,\ldots,k\}-\{4\}\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Hence, we may assume that \(\mathcal W_4\cup \mathcal W_5=\emptyset\). Therefore \(\mathcal{W}=\mathcal{W}_1\cup \mathcal{W}_2\cup \mathcal{W}_3\). For each \(i\in \{1,2,3\}\), let \(m_i=|\mathcal{W}_i|\). Then we have that \(n=|M|+m_1+2m_2+3m_3\) and \(m_1+m_2+m_3\ge 3\). First let \(|M|=2\) and let \(\mathcal{W}_3=\{v_1^iv_2^iv_3^i | 1\le i\le m_3\}\) if \(\mathcal W_3\neq\emptyset\) and \(\mathcal{W}_2=\{w_1^jw_2^j | 1\le j\le m_2\}\) when \(\mathcal W_2\neq\emptyset\). If \(\mathcal W_3\neq \emptyset\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(y)=1\) for \(y\in M\), \(g(v_1^i)=g(v_3^i)=1\) for each \(1\le i\le m_3\), \(g(w^j_2)=1\) for each \(1\le j\le m_2\) and \(g(y)=0\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. Therefore assume that \(\mathcal W_3=\emptyset\). If \(m_2\ge 2\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(y)=1\) for \(y\in M\), \(g(w^1_1)=1\), \(g(w^j_2)=1\) for each \(2\le j\le m_2\) and \(g(y)=0\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. If \(m_2=1\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(y)=1\) for \(y\in M\), \(g(w^1_1)=g(w^1_2)=1\) and \(g(y)=0\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3 since \(m_1\ge 2\). If \(m_3=m_2=0\), then let \(z\in V(G)-M\) and define the function \(g:V({G})\to \{0,1,2\}\) by \(g(y)=1\) for \(y\in M\cup \{z\}\) and \(g(y)=0\) otherwise. Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Henceforth, we may assume that \(|M|\ge 3\). First let there are two vertices \({v,u}\in M\) such that \(\deg_G(u),\deg_G(v)\ge 4\) and there is an \(M\)-ear path \(uWv\) in \({F}\). Let \({G}'={G}-V(W)\) and \(W=v_1v_2\ldots v_k\). By assumption we have \(k\in \{1,2,3\}\) and \({G}'\in {\mathcal{R}}\). By the induction hypothesis on \(G'\), it has a total Roman \(\{2\}\)-dominating function \(f\) such that \(f(u),f(v)\ge 1\). If \(k=1\), then \(f\) can be extended to a total Roman \(\{2\}\)-dominating function of \({G}\) by labeling a 0 to \(v_1\), if \(k=2\), then \(f\) can be extended to a total Roman \(\{2\}\)-dominating function of \({G}\) by labeling a 0 to \(v_1\) and 1 to \(v_2\), and if \(k=3\), then \(f\) can be extended to a total Roman \(\{2\}\)-dominating function of \({G}\) by labeling a 0 to \(v_2\) and 1 to \(v_1,v_3\). In either case we obtain a total Roman \(\{2\}\)-dominating function of \({G}\) with weight at most \(\frac{5n}{6}\) with desired property. Thus we may assume that there is no \(M\)-ear path \(uWv\) such that \(\deg_G(u),\deg_G(v)\ge 4\). We distinguish two cases.

Case 1. \(\mathcal W_3\neq \emptyset\).

Let \(W=x_1x_2x_3\in \mathcal{W}_3\) and \(ux_1x_2x_3v\) be a path in \({G}\) where \({v, u}\in M\). By assumption, we may assume without loss generality that \(\deg_G(u)=3\). We distinguish the following situations.

Subcase 1.1. \(u\) is joined to three \(M\)-ear paths in \(\mathcal{W}_3\).

Let \(W_2=y_1y_2y_3\) and \(W_3=z_1z_2z_3\) be two \(M\)-ear paths in \(\mathcal{W}_3\) different from \(W\), such that \(uz_1,uy_1,{tz_3,} t'y_3\in E({G})\).

Suppose that the graph \({G}'\) is obtained from \({G}-\cup_{i=2}^3\{x_i,y_i,z_i\}\) by joining \(x_1\), \(y_1\) and \(z_1\) to \(v\), \(t'\) and \(t\), respectively. Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-6)}{6}\) and that labels by positive values any vertex of degree at least 3.

In particular, \(\min\{f({u}),f(t),f(t')\}\ge 1\). To total dominate \({u}\), we can suppose that \(f(x_1)\ge 1\). Define \(g:V({G})\to \{0,1,2\}\) by \(g(x_3)=g(y_1)=g(z_1)=g(y_3)=g(z_3)=1\), \(g(y_2)=g(z_2)=g(x_2)=0\) and \(g(y)=f(y)\) otherwise. Clearly, \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+5\le \frac{5(n-6)}{6}+5=\frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 1.2. \({u}\) is adjacent to two \(M\)-ear paths in \(\mathcal{W}_3\) and to an \(M\)-ear path in \(\mathcal{W}_2\).

Let \(W_2=y_1y_2y_3\in\mathcal W_3\) be the other \(M\)-ear paths in \(\mathcal{W}_3\) and\(W_3=z_1z_2\in \mathcal W_2\) such that \({u}z_1,{u}y_1\in E({G})\). {Assume that {\(ty_3, t’z_2\in E({G})\), and} let {the graph \({G}’\) be obtained from \(G-\{x_2,x_3,y_2,y_3,z_2\}\) {{by joining \(x_1\), \(y_1\) and \(z_1\) to \({v}\), \(t\) and \(t’\), respectively}. Clearly, \({G}’\in {\mathcal{R}}\). By the induction hypothesis, there exists a {total Roman \(2\)-dominating function} \(f\) of \({G}’\) {of weight \(\omega(f)\le \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3.

In particular, \(f({u})\geq 1\). To total dominate \({u}\), we can suppose that \(f(x_1)\ge 1\). Define \(g:V({G})\to \{0,1,2\}\) by \(g(x_3)=g(y_1)=g(y_3)={ g(z_1)=1}\), \(g(x_2)=g(y_2)=g(z_2)=0\) and {\(g(y)=f(y)\)} otherwise. Clearly \(g\) is a {total Roman \(\{2\}\)-dominating function} {of \({G}\) of weight \(\omega(g)=\omega(f)+4 \leq \frac{5(n-5)}{6}+4 < \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 1.3. \({u}\) is adjacent to two \(M\)-ear paths in \(\mathcal{W}_3\) and to a \(M\)-ear path in \(\mathcal{W}_1\).

Let \(W_2=y_1y_2y_3\in\mathcal W_3\) be the other \(M\)-ear paths in \(\mathcal{W}_3\) and \(W_3=t''\in \mathcal W_1\) such that \({ut'',}{u}y_1,ty_3,t't''\in E({G})\). First let \(M\) be the set of all vertices of degree at least three and independent in \({G}\). First let \(|\{{v},t,t'\}|=3\). Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,x_3,{u},y_1,y_2\}\) by joining \(y_3\) and \(t''\) to \({v}\) and \(t\), respectively.

Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) such that \(f\) assigns a positive value for any vertex of degree at least three, and \(\omega(f)\le \frac{5(n-6)}{6}\). If \(f(y_3)+f(t'')= 0\), then the function \(g:V({G})\to \{0,1,2\}\) define by \(g(x_3)=0\), \(g(x_1)=g(x_2)=g(y_1)=g(y_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+5\le \frac{5(n-6)}{6}+5= \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

If \(f(y_3)=1\), then the function \(g:V({G})\to \{0,1,2\}\) by \(g(y_2)=g(x_2)=0\), \(g(x_1)=g(x_3)=g({u})=g(y_1)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+4\le \frac{5(n-6)}{6}+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

For the next, we can assume that \(|\{v,t,t'\}|<3\). Suppose that \(t=t'\) and \(t\in M-\{{v, u}\}\) (the case \({v}=t'\) and \({v}\in M-\{{u},t\}\) is similar). Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,y_1,y_2,{u},t''\}\) by joining \(x_3\) and \(y_3\) to \(t=t'\) and \({v}\), respectively. Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-6)}{6}\) and that labels by positive values any vertex of degree at least 3.

If \(f(x_3)\ge 1\) (the case \(f(y_3)\ge 1\) is similar), then the function \(g:V({G})\to \{0,1,2\}\) by \(g(x_2)=0\), \(g(x_1)={g({u})=}g(y_1)=g(y_2)=g(t'')=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+5\le \frac{5(n-6)}{6}+5= \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Assume that \(f(x_3)+f(y_3)=0\). Then the function \(g:V(G)\to \{0,1,2\}\) by \(g(t'')=0\), \(g(x_1)=g(x_2)=g({u})=g(y_1)=g(y_2)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+5\le \frac{5(n-6)}{6}+5= \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Next assume that \(t={v}\) and \({v}\neq t'\). Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,y_1,y_2,t'',{u}\}\) by joining \(t'\) to \(x_3\) and \(y_3\). A method similar to that described above we can see that \(\omega(g)\le \frac{5n}{6}\).

Finally suppose that \({v}=t=t'\). Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,y_1,{u}\}\) by joining \(y_2\) to \(x_3\) and \(t''\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) such that \(f\) labels a positive value for any vertex of degree at least three and \(\omega(f)\le \frac{5(n-4)}{6}\). Then \(f(y_2)\ge 1\). If \(f(y_3)=1\), the function \(g:V({G})\to \{0,1,2\}\) by \(g(y_1)=0\), \(g(x_1)=g({u})=g(x_2)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) such that \(g\) labels a positive value for any vertex of degree at least three, and we have \(\omega(g)=\omega(f)+3\le \frac{5(n-4)}{6}+3< \frac{5n}{6}\). Assume that \(f(y_3)=0\). Then \(f(t'')+f(x_3)\ge 1\), and the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(t'')=g(x_3)=g(y_1)=0\), \(g(x_1)=g(x_2)=g({u})=g(y_3)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) of weight \(\omega(g)=\omega(f)+3\le \frac{5(n-4)}{6}+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 1.4. \({u}\) is adjacent to an \(M\)-ear path in \(\mathcal{W}_3\) and is adjacent to two \(M\)-ear paths in \(\mathcal{W}_2\).

Let \(W_i=y^i_1y^i_2\in\mathcal W_2\) for \(i\in\{1,2\}\) such that \({u}y^1_1, {u}y^2_1,ty^1_2,t'y^2_2\in E({G})\). Let the graph \({G}'\) be obtained from \({G}-\{x_1,{u},y^1_1,y^2_1\}\) by joining \(x_2\) to \(y_2^i\) for \(i\in \{1,2\}\). Clearly, \({G}'\in { \mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3.

In particular, \(\min\{f(x_2),f(t),f(t')\}\ge 1\). Also to totally dominate \(x_2\) we must have \(f(x_3)+f(y_2^1)+f(y_2^2)\ge 1\). If \(f(x_3)\ge 1\), then the function \(g:V(G)\to \{0,1,2\}\) by \(g(x_1)=0\), \(g(y_1^1)=g({u})=g(y_1^2)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) of weight \(\omega(g)=\omega(f)+3\le \frac{5(n-4)}{6}+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. If \(f(y_2^1)\ge 1\) (the case \(f(y_2^2)\ge 1\) is similar), then the function \(g:V({G})\to \{0,1,2\}\) by \(g(y_1^1)=0\), \(g(x_1)=g({u})=g(y_1^2)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 1.5. \({u}\) is adjacent to an \(M\)-ear path in \(\mathcal{W}_3\), an \(M\)-ear path in \(\mathcal{W}_2\) and an \(M\)-ear path in \(\mathcal{W}_1\).

Let \(W_2=y_1y_2\in \mathcal W_2\) and \(W_3=t''\in \mathcal {W}_1\) such that \({u}y_1,{u}t''\in E(G)\) and \(ty_2, t't''\in E(G)\). We consider the following situations.

(a) \(|\{{v},t,t'\}|=3\).
Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,x_3,{u},y_1,\}\) by joining \({v}\) and \(t''\) to \(y_2\) and \(t\), respectively. Clearly \(G'\in {\mathcal{R}}\) and by the induction hypothesis, \({G}'\) has a total Roman \(\{2\}\)-dominating function \(f\) of weight \(\omega(f)\le \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3. If \(f(y_2)=f(t'')=0\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_1)=0\), \(g(x_2)=g(x_3)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+4\le \frac{5(n-5)}{6}+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. If \(f(y_2)\ge 1\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_1)=g(y_1)=0\), \(g(x_2)=g(x_3)=g({u})=1\), \(g(t'')=\max\{1,f(t'')\}\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) of weight \(\omega(g)=\omega(f)+4\le \frac{5(n-5)}{6}+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. If \(f(y_2)=0, f(t'')\ge 1\), then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_1)=g(y_1)=0\), \(g(x_2)=g(x_3)=g({u})=g(y_2)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) of weight \(\omega(g)=\omega(f)+4\le \frac{5(n-5)}{6}+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

(b) \(t=t'\) and \({v}\neq t\).
Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,x_3,{u},y_1,\}\) by joining \(v\) to \(y_2\) and \(t''\). Clearly \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, \({G}'\) has a total Roman \(\{2\}\)-dominating function \(f\) of weight \(\omega(f)\le \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(x_1)=0\), \(g(x_2)=g(x_3)=g({u})=g(y_1)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+4\le \frac{5(n-5)}{6}+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

(c) \({v}=t\) and \({v}\neq t'\).
Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,x_2,y_1,t''\}\) by joining \(t'\) to \(x_3\) and \(y_2\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(t'')=0\), \(g(x_1)=g(x_2)=g(y_1)={g({u})=}1\) and \(g(y)=f(y)\) otherwise, if \(f(x_3)=f(y_2)=0\), by \(g(x_2)=0\), \(g(x_1)=g(y_1)=g({u})=g(t'')=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_3)\ge 1\), and by \(g(y_1)=0\), \(g(x_1)=g(x_2)=g({u})=g(t'')=1\) and \(g(y)=f(y)\) otherwise, when \(f(y_2)\ge 1\). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

(d) \({v}=t'\) and \({v}\neq t\).
Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,x_2,y_1,y_2\}\) by joining \(t\) to \(x_3\) and \(t''\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(y_2)=0\), \(g(x_1)=g(x_2)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_3)=f(t'')=0\), by \(g(x_2)=0\), \(g(x_1)=g(y_1)=g(y_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_3)\ge 1\), and by \(g(y_1)=0\), \(g(x_1)=g(x_2)=g({u})=g(y_2)=1\) and \(g(y)=f(y)\) otherwise, when \(f(t'')\ge 1\). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

(e) \({v}=t=t'\).
Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,y_1\}\) by joining \(x_2\) to \(y_2\) and \(t''\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) such that \(f\) of weight \(\omega(f)\le \frac{5(n-3)}{6}\) and that labels by positive values any vertex of degree at least 3. Then \(f(x_2)\ge 1\), and without loss of generality, \(f(x_3)\ge 1\). Now the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(t'')=g(y_2)=g(x_1)=0\), \(g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \(G\) of weight \(\omega(g)=\omega(f)+2< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 1.6. \({u}\) is adjacent to an \(M\)-ear path in \(\mathcal{W}_3\) and is adjacent to two \(M\)-ear paths in \(\mathcal{W}_1\).

Let \(W_1=y_1,\) \(W_2=y_2\in\mathcal W_1\) such that \({u}y_1,{u}y_2,y_1t, y_2t'\in E({G})\). Consider the following situations.

• \({v}\not\in \{t,t'\}\).
  Suppose that the graph \({G}'\) is obtained from \({G}-\{x_1,x_2,x_3,{u}\}\) by joining \({v}\) to \(y_1\) and \(y_2\). Clearly, \({G}'\in {\mathcal{R}}\). By the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Then the function \(g:V({G})\to \{0,1,2\}\) defined by \(g(x_2)=0\), \(g(x_1)=g(x_3)=g({u})=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

• \({v=t}\) and \({v\neq t'}\).
  Assume that \({G}'\) is obtained from \(G-\{x_1,x_2,{u},y_2\}\) by joining \(t'\) to \(x_3\) and \(y_1\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(y_2)=0\), \(g(x_1)=g(x_2)=g({u})=1\) and \(g(y)=g(y)\) otherwise, if \(f(x_3)=f(y_1)=0\), by \(g(x_2)=0\), \(g(x_1)=g(y_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_3)\ge 1\), and by \(g(y_1)=0\), \(g(x_1)=g(x_2)=g({u})=g(y_2)=1\) and \(g(y)=f(y)\) otherwise, when \(f(y_1)\ge 1\). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

• \({v}=t=t'.\)
  Assume that \({G}'\) is obtained from \({G}-\{x_1,{u}\}\) by joining \(x_2\) to \(y_1\) and \(y_2\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-2)}{6}\) and that labels by positive values any vertex of degree at least 3. Then \(f(x_2)\ge 1\)1, and without loss of generality, \(f(x_3)\ge 1\). Define \(g:V(G)\to \{0,1,2\}\) by \(g(x_2)=g(y_1)=g(y_2)=0\), \(g(x_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise. Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+1< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Considering Case 1, we may assume that \(\mathcal{W}_3=\emptyset\).

Case 2. \(\mathcal W_2\neq \emptyset\).

Let \(W_1=x_1x_2\in \mathcal{W}_2\) and \(ux_1x_2v\) be a path in \({G}\). Suppose, without loss of generality, that \(\deg_G({u})=3\). Consider the following subcases.

Subcase 2.1. \({u}\) is adjacent to three \(M\)-ear paths in \(\mathcal{W}_2\).

Let \(W_2=y_1y_2\) and \(W_3=t”_1t”_2\) be the other \(M\)-ear paths in \(\mathcal{W}_2\) such that \({u}t”_1,{u}y_1\in E({G})\) and let \(ty_2,t’t”_2\in E({G})\) where \(t,t’\in M\). First let \(|\{{v},t,t’\}|\geq 2\) and let without loss of generality that \({v}\not\in \{t,t’\}\). {Assume that \({G}’\) is obtained from \({G}-\{{u},x_1,x_2,y_1,t_1”\}\) and by joining \({v}\) to \(y_2\) and {\(t”_2\)}. Clearly, \({G}’\in {\mathcal{R}}\) and by the induction hypothesis, there exists a {total Roman \(\{2\}\)-dominating function} \(f\) of \({G}’\) {of weight \(\omega(f)\leq \frac{5(n-5)}{6}\) and that labels by positive values any vertex of degree at least 3. Define the function \(g:V({G})\to \{0,1,2\}\) by {\(g({u})=g(y_1)=g(x_1)=g(t_1”)=1\)}, \(g(x_2)=0\) and {\(g(y)=f(y)\)} {otherwise}, when {\(f(y_2)=f(t_2”)=0\)}, by {\(g({u})=g(x_2)=g(x_1)=g(t_1”)=1\)}, \(g(y_1)=0\) and {\(g(y)=f(y)\)} {otherwise}, when \(f(y_2)\geq 1\), and by {\(g({u})=g(x_2)=g(x_1)=g(y_1)=1\)}, \(g(t_1”)=0\) and {\(g(y)=f(y)\)} {otherwise}, when {\(f(t_2”)\ge 1\).} Clearly \(g\) is a {total Roman \(\{2\}\)-dominating function} of \({G}\) of weight \(\omega(g)=\omega(f)+4< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.}

Now let \({v}=t=t'\).

Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},y_1,t''_1\}\) and by joining \(x_1\) to \(y_2\) and \(t''_2\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-3)}{6}\) and that labels by positive values any vertex of degree at least 3.

Then \(f(x_1)\ge 1\) and \(\max \{f(x_2),f(y_2),f(t''_2)\}\ge 1\). Define \(g:V({G})\to \{0,1,2\}\) by \(g(x_1)=g(y_2)=g(t''_2)=0\), \(g(x_2)=g({u})=g(y_1)=g(t''_1)=1\) and \(g(y)=f(y)\) otherwise, is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+2< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 2.2. \({u}\) is adjacent to two \(M\)-ear paths in \(\mathcal{W}_2\) and adjacent to an \(M\)-ear path in \(\mathcal{W}_1\).

Let \(W_2=y_1y_2\) be another \(M\)-ear path in \(\mathcal{W}_2\) and \(W_3=t''\) be a \(M\)-ear path in \(\mathcal{W}_1\) such that \({u}y_1,{u}t''\in E(G)\). Suppose \(ty_2,t't''\in E({G})\) where \(t,t'\in M\). We consider the following.

• \({v}\not\in \{t,t'\}\). Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,x_2,y_1\}\) and by joining \({v}\) to \(y_2\) and \(t''\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V(G)\to \{0,1,2\}\) by \(g(x_2)=0\), \(g(x_1)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(t'')=f(y_2)=0\), by \(g(y_1)=0\), \(g(x_1)=g(x_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(y_2)\ge 1\), and by \(g(x_1)=0\), \(g(x_2)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, when \(f(t'')\ge 1\). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

• \({v}=t\) and \({v}\neq t'\).
  Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,y_1,t''\}\) by adding the edges \(t'x_2\) and \(t'y_2\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(t'')=0\), \(g(x_1)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_1)=f(y_1)=0\), by \(g(x_1)=0\), \(g(y_1)=g(t'')=g({u})=1\) and \(g(y)=f(y)\) otherwise, when \(f(x_2)\ge 1\) (the case \(f(y_2)\ge 1\) is similar). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

• \({v}=t'\) and \({v}\neq t\).
  Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},y_1,y_2,x_1\}\) by adding the edges \(tx_2\) and \(tt''\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \(G'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V({G})\to \{0,1,2\}\) by \(g(y_2)=0\), \(g(x_1)=g(y_1)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(t'')=f(x_2)=0\), by \(g(x_1)=0\), \(g(y_1)=g(y_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, if \(f(x_2)\ge 1\), and by \(g(t'')=g(y_1)=0\), \(g(x_2)=g(x_1)=g(y_2)=g({u})=1\) and \(g(y)=f(y)\) otherwise, when \(f(t'')\ge 1\). Clearly \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

• \({v}=t=t'\).
  Let \(w\in M-\{u,v\}\) and \(w'\) be a neighbor of \(w\) in \({G}\). Suppose that the graph \({G}'\) is obtained from \({G}-\{{u},x_1,x_2,y_1\}\) by adding the edges \(wy_2\) and \(wt''\). Clearly, \({G}'\in {\mathcal{R}}\) and by the induction hypothesis, there exists a total Roman \(\{2\}\)-dominating function \(f\) of \({G}'\) of weight \(\omega(f)\le \frac{5(n-4)}{6}\) and that labels by positive values any vertex of degree at least 3. Define \(g:V(G)\to \{0,1,2\}\) by \(g(x_2)=0\), \(g({u})=g(x_1)=g(y_1)=1\) and \(g(y)=f(y)\) otherwise, if \(f(y_2)=f(t'')=0\), and by \(g(w')=\max\{1,f(w')\}\), \(g(x_1)=g(y_2)=g(t'')=0\), \(g({u})=g(x_2)=g(y_1)=1\) and \(g(y)=f(y)\) otherwise, if \(f(y_2)+f(t'')\ge 1\). Clearly, \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)=\omega(f)+3< \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3.

Subcase 2.3. The other neighbor of \({u}\) belong to \(M\)-ear paths in \(\mathcal{W}_1\). Considering above cases and subcases, we can suppose that any vertex of \(M\) is adjacent to at most one vertex in \(\bigcup_{W\in \mathcal W_2}V(W)\). Then \({G}\) is a graph obtained from a loopless multigraph \({G}'\) by subdividing each edge of \({G}'\) at most twice such that the set of edges of \({G}'\) subdivided twice forms a matching in \({G}'\). Note that \(W=|V({G})|\ge |V({G}')|+|E({G}')|\ge |V({G}')|+\frac{3|V({G}')|}{2}=\frac{5|V({G}')|}{2}\) because \(\deg_{G'}(y)\ge 3\) for any \(y\in V(G')\). Let \(M=\{e_1={u_1v_1,\ldots,e_{k}=u_{k}v_{k}}\}\) be set of edges of \({G}'\) subdivided twice and let the edge \({u}_i{v}_i\) be replaced by \({u}_iw_1^iw_2^i{v}_i\) for \(1\le i\le k\). For each vertex \(x\) in \(V({G}')\setminus \{{u}_1,\ldots,{u}_{k}\}\), let \(x'\) be one of its neighbors in \({G}\). Define the function \(g: V({G})\to \{0,1,2\}\) by \(g(u_i)=g(w_1^i)=1\) for \(1\le i\le k\), \(g(x)=g(x')=1\) for \(x\in V(G')\setminus \{{u}_1,\ldots,{u}_{k}\}\), and \(g(y)=0\) otherwise. Clearly, \(g\) is a total Roman \(\{2\}\)-dominating function of \({G}\) of weight \(\omega(g)\le2|V({G}')|< \frac{\frac{5|V({G}')|}{2}\times 5}{6}\le \frac{5n}{6}\) and that labels by positive values any vertex of degree at least 3. \(\ \Box\)

3. Main Result

In this section we prove our main result.

Acknowledgments

The authors are deeply thankful to the reviewer for his/her valuable suggestions to improve the quality of this manuscript. H. Abdollahzadeh Ahangar was supported by the Babol Noshirvani University of Technology under research grant number BNUT/385001/00.