Some Results Of Double Roman Domination Number With 2-independence And Annihilation Number On Trees

Let G=(V,E)be a graph with the vertex set V and the edge set E.A function f:V→{0,1,2,3} is a double Roman dominating function on a graph G if the following conditions hold:(1)if f(v)=0,then there must have one neighbor of v denoted by u such that f(u)=3,or at least two neighbors of v denoted by v1,v2 such that f(v1)=f(v2)=2;(2)if f(v)=1,then there must have at least one neighbor of v denoted by u such that f(u)=3.The double Roman dominating number γdR(G)equals the minimum weight of a double Roman dominating function on G.A subset X of V is 2-independent if the maximum degree of the subgraph induced by X is at most 1.The 2-independence number β2(G)is the maximum cardinality among all 2-independent sets of G.Let d1,d2,…,dn be the degree sequence of a graph G arranged in non-decreasing order,the annihilation number a(G)is the largest integer k such that the sum of the first k terms of the non-decreasing degree sequence of G is at most the number of edges in G.We said G is a single cycle graph if it has one and only one induced subgraph as a cycle,and at most one vertex on the cycle has a degree strictly greater than 2.The diameter of G denoted by P=vOv1…vd and vo is farthest vertex to vd.First,in this thesis we study the relationship between the double Roman dominating number and the 2-independence number on a tree T:γdR(T)≤5/3β2(T).Secondly,let T1=P4,attach a path P4=xyzw by joining y to a support vertex of Ti to obtain Ti+1.We provide a constructive characterization of all trees T that is a family T={T1,T2,...,Tk} satisfying γ(T)=γ’(T).Then,on the basis of Zhang et al[20]proposing a linear time algorithm which is used to compute the double Roman domination number of a tree,we obtain a linear time algorithm for calculating the double Roman domination number on a single cycle graph.Finally,by selecting a diameter path in the tree,we give an upper bound of the double Roman domination number in the sight of the annihilation number by mathematical induction,that is γdR(T)≤2a(T)+1.