(1.School of Puyang Innovation High School,Puyang 457000,China;2.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China)

Abstract: For a graph G(V,E),a Roman {2}-dominating function f:V →{0,1,2} has the property that for every vertex v V with f(v)0,either v is adjacent to at least one vertex u for which f(u)2,or at least two vertices u1 and u2 for which f(u1)f(u2)1.A Roman {2}-dominating function f(V0,V1,V2) is called independent if V1 ∪V2 is an independent set.The weight of an independent Roman {2}-dominating function f is the value ω(f)∑vV f(v),and the independent Roman {2}-domination number i{R2}(G)is the minimum weight of an independent Roman {2}-dominating function on G.In this paper,we characterize all trees with i{R2}(T)γ(T)+1,and give a linear time algorithm to compute the value of i{R2}(T) for any tree T.

Keywords: Domination number;Roman {2}-dominating function;Independent Roman{2}-domination number

§1.Introduction

For notion and graph theory terminology not defined here we follow [4].LetG(V,E)be a graph with vertex setVV(G) and edge setEE(G).For any vertex,theopen neighborhood N(v)ofvconsists of the vertices adjacent tov,that is,N(v).Theclosed neighborhoodofvisN[v]N(v)∪{v}.ThedegreeofvinG,denoted bydG(v),is the cardinality of its open neighborhood,that is,dG(v)|N(v)|.A vertex of degree one is called aleafand its neighbor is called asupport vertex.An edge incident with a leaf is called apendent edge.A vertexis said to have aprivate neighborwith respect to the setSif there exists a vertex(v)∩(V -S) for whichN(w)∩S{v}.

Atreeis an acyclic connected graph.A tree is adouble starif it contains exactly two vertices of degree at least two.A double star with respectivelyrandsleaves attached at each support vertex is denoted bySr,s.Thesubdivision graph S(G)of a graphGis obtained fromGby replacing each edgeuvofGby a new vertexwand edgesuw,wv.

For positive integersrands,letFr,sbe the tree obtained from a double starSr,sby subdividing every edge exactly once.LetFbe the family of all such treesFr,s,that is,F{Fr,s|r,s≥1}.Letbe the vertices with degreesr+1 ands+1,respectively.The new vertex resulting from the subdivision of the edgexyis called thecenter vertexofFr,s.

Lett≥2,a tree is ahealthy spiderif we subdivide all edges of a starK1,t,and a healthy spider is also called asubdivided star.Awounded spideris the graph formed by subdividing some edges (at mostt-1 edges) of a starK1,t.The unique center ofK1,tis also called thehead vertexof a spider treeTand the vertex at distance two from the head vertex is called thefoot vertex.

Letpbe a positive integer.A subsetS ?Vis ap-domination setof a graphGif every vertex ofV -Shas at leastpneighbors inS,in other words,|N(v)∩S|≥pfor every vertex.Thep-domination number γp(G) is the minimum cardinality among thep-domination sets ofG.Note that the 1-domination numberγ1(G) is the usualdomination number γ(G).Ap-domination set of minimum cardinality of a graphGis also called aγp(G)-set.

A functionf:V →{0,1,2}is aRoman dominating functiononGif every vertexvwithf(v)0 is adjacent to at least one vertexufor whichf(u)2.The weight of a Roman dominating function is the valueω(f)∑(v).It is worth mentioning that Roman dominating function has been studied by many authors,for example,see [2,3,5].In [1,6,7] there are some new variants of Roman domination.ARoman {2}-dominating function f:V →{0,1,2}has the property that for every vertexwithf(v)0,either there is at least one vertex(v)withf(u)2 or at least two verticesu1,u2(v) withf(u1)f(u2)1.The weight of a Roman{2}-dominating function is the valueω(f)∑(v),and the minimum weight of a Roman{2}-dominating functionfis theRoman {2}-domination number,denotedγ{R2}(G).

A subsetD ?Visindependentif no two vertices inDare adjacent.A functionfis calledindependent Roman {2}-dominating function(IR2DF) iffis a Roman{2}-dominating function andV1∪V2is an independent set.The weight of an independent Roman{2}-dominating functionfis the valueω(f)∑(v).The minimum weight of an independent Roman{2}-dominating function on a graphGis called theindependent Roman {2}-dominating number i{R2}(G) ofG.We say that a function ofGis ani{R2}(G)-functionif it is an independent Roman{2}-dominating function andω(f)i{R2}(G).

LetVi(v)i}fori0,1,2.Note that there exists a 1-1 correspondence between the functionfand the partition (V0,V1,V2) ofV,then we can writef(V0,V1,V2).

Rahmouni et al.[6] showed that IR2D is NP-complete for bipartite graphs,and they proposed the following problem.

Problem 1.Can you design a linear algorithm for computing the value ofi{R2}(T) for any treeT?

In this paper,we characterize all trees withi{R2}(T)γ(T)+1,and give a linear time algorithm to compute the value ofi{R2}(T) for any treeT.

§2.A characterization of trees T with i{R2}(T)γ(T)+1

The following results play an important role in this paper.

Lemma 2.1.([8]) For any nontrivial tree T,γ2(T)≥γ(T)+1.

Lemma 2.2.([8]) A nontrivial tree T satisfies γ2(T)γ(T)+1if and only if T is a subdivided star or a subdivided star minus a leaf or a subdivided double star.

Theorem 2.1.For any nontrivial tree T,i{R2}(T)≥γ(T)+1.

Proof.Letf(V0,V1,V2) be an arbitraryi{R2}-function ofT.IfV2φ,thenV1is a 2-domianting set ofT,we obtain thati{R2}(T)|V1|≥γ2(T).By Lemma 2.1,we have

Next we assume thatV2/φ,sinceV1∪V2is also a dominating set ofT,we have

Therefore,γ(T)+1≤i{R2}(T).

Proposition 2.1.If T ?F,then i{R2}(T)γ(T)+1.

Proof.LetT～Fr,s.Note that ther+sleaves together with the center vertex ofTconsist of a dominating set,denoted byS.For every pair of distinct verticesuandvinS,it holds thatdG(u,v)≥3.Clearly,γ(T)≥|S|.Sor+s+1≥γ(T)≥|S|r+s+1.Therefore,γ(T)r+s+1.Define the functionfonTby assigning the value 1 to ther+sleaves and the two neighbors of the center vertex ofT,and the value 0 to the remaining vertices.Clearlyf(V0,V1,V2) is an independent Roman{2}-dominating function onT.By Theorem 2.1,

We havei{R2}(T)γ(T)+1.

Proposition 2.2.If T is a spider,then i{R2}(T)γ(T)+1.

Proof.IfTis a healthy spider,we knowTis obtained from a starK1,tby subdividing every edge exactly once.In this case,γ(T)t.We define a functionfonTby assigning the value 1 to the head vertex and thetfoot vertices,and the value 0 to the remaining vertices.Clearlyf(V0,V1,V2) is an independent Roman{2}-dominating function onT.Thus,

By Theorem 2.1,

The result is valid.

Now letTbe a wounded spider.Without loss of generality,we assume thatTis obtained from a starK1,tby subdividingjedges exactly once,1≤j ≤t-1.In this case,γ(T)j+1.Define a functionfonTby assigning the value 2 to the head vertex,the value 1 to thejfoot vertices and the value 0 to the remaining vertices.Clearlyf(V0,V1,V2) is an independent Roman{2}-dominating function.Thus

By Theorem 2.1,

Consequently,i{R2}(T)γ(T)+1.

Theorem 2.2.A nontrivial tree T satisfies i{R2}(T)γ(T)+1if and only if T is a subdivided star or a subdivided double star or a wounded spider.

Proof.The sufficiency follows from Proposition 2.1 and Proposition 2.2.Hence,it suffices to prove the necessity.Letf(V0,V1,V2)be an arbitraryi{R2}-function ofT.SinceDV1∪V2is also a dominating set ofT,we have|V1|+|V2|≥γ(T).Thus

implying that|V2|≤1.We consider the following two cases.

Case 1.|V2|0.Since every vertex inV0is adjacent to at least two vertices inV1,V1is also a 2-dominting set ofT,we have|V1|≥γ2(T).By Lemma 2.1,

Therefore,γ2(T)γ(T)+1.By Lemma 2.2,ifγ2(T)γ(T)+1,thenTis a subdivided star or a subdivided star minus a leaf or a subdivided double star.

IfTis a subdivided star minus a leaf,the head vertexxhas exactly one leaf neighborywithf(y)0,1}.Iff(y)0,thenf(x)2,a contradiction to the fact that|V2|0.Now assume thatf(y)1.Since|V2|0,we observe that all foot vertices ofTare assigned the value 1 andf(x)1,V1is not independent,a contradiction.Therefore,ifTsatisfiesi{R2}(T)γ(T)+1 and|V2|0,thenTis a subdivided star or a subdivided double star.

Case 2.|V2|1.Without loss of generality,we assume thatV2{u}.Since

we haveγ(T)|V1|+|V2|,that is to say,DV1∪V2is aγ-set ofT.ThenDV1∪V2is an independent set.

Claim 1.There is no two vertices in V1that have common neighbors.

Proof of Claim 1.Suppose that there exists two verticesv1,v21such thatv1andv2have at least one common neighbor.Ifv1andv2have at least two common neighborsw1,w20,thenv1w1v2w2v1is a cycle,contradicting the fact thatTis a tree.Ifv1andv2have exactly one common neighbor0,letD′D{v1,v2}∪{w},we observe thatD′is also a dominating set ofTand|D′|＜|D|,contradicting the fact thatDis aγ-set.

Claim 2.u has at least one private neighbor.

Proof of Claim 2.By the connectivity ofT,uhas at least one neighbor inV0.Supposeuhas no private neighbors.By Claim 1,every neighbor ofuis adjacent to exactly one vertex inV1.Reassigning 1 to the vertexuand other vertices remain unchanged produces a new independent Roman{2}-dominating functionf′ofTsuch thatf′(T)＜f(T),a contradiction.

Claim 3.V0?N(u).

Proof of Claim 3.It is obvious that Claim 3 holds for private neighbors ofu.Letzbe a vertex which is not a private neighbor ofu.Ifzis not a neighbor ofu,then it must be adjacent to at least two vertices inV1,a contradiction to Claim 1.

Claim 4.Every vertex in V1has exactly one neighbor in V0.

Proof of Claim 4.SinceV1∪V2is independent,N(v)?V0for every vertex1.Assume that there is a vertex1with at least two neighborsz1,z20.By Claim 3,z1andz2are neighbors ofu.Thus,vz1uz2vis a cycle,a contradiction.

Claim 5.V0is an independent set.

Proof of Claim 5.Suppose there exists an edge(V0),by Claim 3,xandyare neighbors ofu.Thus,xyuis a cycle,a contradiction.

By Claim 1-5,Tis a wounder spider with head vertexu.This completes the proof of Theorem 2.2.

§3.A linear time algorithm for independent Roman{2}-domination in trees

For any graphG,(G) and(G).We define

Proposition 3.1.For any graph G,uV(G),we have

Theorem 3.1.Let G1and G2(G1)(G2),and let G be the graph obtained from the disjoint union G1and G2by adding a new edge uv.Then

Proof.(i) It follows from the fact thatfis an independent Roman{2}-dominating function ofGwithf(u)0 if and only ifff′∪f′′,wheref′is an independent Roman{2}-dominating function ofG1withf′(u)0 andf′′is an independent Roman{2}-dominating function ofG2withf′′(v)0,f′is an independent Roman{2}-dominating function ofG1+uvwithf′(u)0,f′(v)1 andf′′is an independent Roman{2}-dominating function ofG2withf′′(v)1.Since the value of vertexvis recorded twice,ω(f)ω(f′)+ω(f′′)-1,orf′is an independent Roman{2}-dominating function ofG1-uandf′′is an independent Roman{2}-dominating function ofG2withf′′(v)2.

(ii) Sincefis an independent Roman{2}-dominating function ofG,iff(u)1,thenf(v)0.Therefore,fis an independent Roman{2}-dominating function ofGwithf(u)1 if and only ifff′∪f′′,wheref′is an independent Roman{2}-dominating function ofG1withf′(u)1 andf′′is an independent Roman{2}-dominating function ofG2+vuwithf′′(v)0,f′′(u)1.Since the value of vertexuis recorded twice,we haveω(f)ω(f′)+ω(f′′)-1.

(iii) Similarly,iff(u)2,thenf(v)0.Therefore,fis an independent Roman{2}-dominating function ofGwithf(u)2 if and only ifff′∪f′′,wheref′is an independent Roman{2}-dominating function ofG1withf′(u)2 andf′′is an independent Roman{2}-dominating function ofG2-v.

(iv) It follows from the fact thatfis an independent Roman{2}-dominating function ofG+uwwithf(u)0,f(w)1 if and only ifff′∪f′′,wheref′is an independent Roman{2}-dominating function ofG1+uwwithf′(u)0,f′(w)1 andf′′is an independent Roman{2}-dominating function ofG2withf′′(v)0,f′is an independent Roman{2}-dominating function ofG1-uandf′′is an independent Roman{2}-dominating function ofG2withf′′(v)1.In this case,since we add the vertexwwithf(w)1 inG,we haveω(f)ω(f′)+ω(f′′)+1,orf′is an independent Roman{2}-dominating function ofG1-uandf′′is an independent Roman{2}-dominating function ofG2withf′′(v)2.Similarly,ω(f)ω(f′)+ω(f′′)+1.

(v) It follows from the fact thatfis an independent Roman{2}-dominating function ofG-uif and only ifff′∪f′′,wheref′is an independent Roman{2}-dominating function ofG1-uandf′′is an independent Roman{2}-dominating function ofG2.By Proposition 3.1,(v) follows.

By Proposition 3.1 and Theorem 3.1,we will give the following dynamic programming algorithm to compute the value ofi{R2}(T).Now we construct a BFS treeTBF SofTrooted ats,wheresis not a leaf,and then compute the depths of all vertices inTBF Sand divide all vertices into layersLi,i0,1,2,...,R,whereRis the height ofTBF S.Note thatRis also equal to the radius ofGwith respect tos.For each vertex,theparentofvis its neighbor inLi-1,i1,2,...,R.We order all vertices according to their level from the higher to the lower level and arbitrarily ordering in the same level.Then we obtain an ordering{v1,v2,...,vn}ofTwithvns.

Algorithm: