A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weig...A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.展开更多
This paper discusses how the infinite set of real numbers between 0 and 1 could be represented by a countably infinite tree structure which would avoid Cantor’s diagonalization argument that the set of real numbers i...This paper discusses how the infinite set of real numbers between 0 and 1 could be represented by a countably infinite tree structure which would avoid Cantor’s diagonalization argument that the set of real numbers is not countably infinite. Likewise, countably infinite tree structures could represent all real numbers, and all points in any number of dimensions in multi-dimensional spaces. The objective of this paper is not to overturn previous research based on Cantor’s argument, but to suggest that this situation may be treated as a definitional or axiomatic choice. This paper proposes a “non-Cantorian” branch of cardinality theory, representing all these infinities with countably infinite tree structures. This approach would be consistent with the Continuum Hypothesis.展开更多
A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken ove...A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.展开更多
Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Th...Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Then majority domination number of a graph G is γ maj(G)=min{f(V)|f is a majority dominating function on G}. We obtain lower bounds on this parameter and generalize some results of Henning.展开更多
Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of...Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of a total dominating set of G. This paper proves that if G is a connected graph with n≥3 vertices and minimum degree at least two.展开更多
Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are...Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.展开更多
This paper studies the strong law of large numbers and the Shannom-McMillan theorem for Markov chains field on Cayley tree. The authors first prove the strong law of large number on the frequencies of states and order...This paper studies the strong law of large numbers and the Shannom-McMillan theorem for Markov chains field on Cayley tree. The authors first prove the strong law of large number on the frequencies of states and orderd couples of states for Markov chains field on Cayley tree. Then they prove the Shannon-McMillan theorem with a.e. convergence for Markov chains field on Cayley tree. In the proof, a new technique in the study the strong limit theorem in probability theory is applied.展开更多
Some strong laws of large numbers for the frequencies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields （NSMC） on Cayley trees are studied. In the proof, a new technique for ...Some strong laws of large numbers for the frequencies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields （NSMC） on Cayley trees are studied. In the proof, a new technique for the study of strong limit theorems of Markov chains is extended to the case of Markov chain fields, The asymptotic equipartition properties with almost everywhere （a,e.） convergence for NSMC on Cayley trees are obtained,展开更多
A vertex subversion strategy of a graph G=(V,E) is a set of vertices S V(G) whose closed neighborhood is deleted from G . The survival subgraph is denoted by G/S . We call S a cut-strategy of G if G/S is disconnected,...A vertex subversion strategy of a graph G=(V,E) is a set of vertices S V(G) whose closed neighborhood is deleted from G . The survival subgraph is denoted by G/S . We call S a cut-strategy of G if G/S is disconnected, or is a clique, or is φ . The vertex-neighbor scattering number of G is defined to be VNS(G)=max{ω(G/S)-|S|} , where S is any cut-strategy of G , and ω(G/G) is the number of the components of G/S . It has been proved that the computing problem of this parameter is NP–complete, so we discuss the properties of vertex-neighbor-scattering number of trees in this paper.展开更多
Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of ...Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.展开更多
Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of tw...Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.展开更多
A new combinatorial interpretation of Raney numbers is proposed. We apply this combinatorial interpretation to solve several tree enumeration counting problems. Further a generalized Catalan triangle is introduced and...A new combinatorial interpretation of Raney numbers is proposed. We apply this combinatorial interpretation to solve several tree enumeration counting problems. Further a generalized Catalan triangle is introduced and some of its properties are proved.展开更多
The independence number of a graph G is the maximum cardinality among all independent sets of G. For any tree T of order n ≥ 2, it is easy to see that . In addition, if there are duplicated leaves in a tree, then the...The independence number of a graph G is the maximum cardinality among all independent sets of G. For any tree T of order n ≥ 2, it is easy to see that . In addition, if there are duplicated leaves in a tree, then these duplicated leaves are all lying in every maximum independent set. In this paper, we will show that if T is a tree of order n ≥ 4 without duplicated leaves, then . Moreover, we constructively characterize the extremal trees T of order n ≥ 4, which are without duplicated leaves, achieving these upper bounds.展开更多
Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16...Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16fc53d.png" width="79" height="20" alt="" /> is said to be a Signed Dominating Function (SDF) if <img src="Edit_c6e63805-bcaa-46a9-bc77-42750af8efd4.png" width="135" height="25" alt="" /> holds for all <img src="Edit_bba1b366-af70-46cd-aefe-fc68869da670.png" width="42" height="20" alt="" />. The signed domination number <img src="Edit_22e6d87a-e3be-4037-b4b6-c1de6a40abb0.png" width="284" height="25" alt="" />. In this paper, we determine the exact value of the Signed Domination Number of graphs <img src="Edit_36ef2747-da44-4f9b-a10a-340c61a3f28c.png" width="19" height="20" alt="" /> and <img src="Edit_26eb0f74-fcc2-49ad-8567-492cf3115b73.png" width="19" height="20" alt="" /> for <img src="Edit_856dbcc1-d215-4144-b50c-ac8a225d664f.png" width="32" height="20" alt="" />, which is generalized the known results, respectively, where <img src="Edit_4b7e4f8f-5d38-4fd0-ac4e-dd8ef243029f.png" width="19" height="20" alt="" /> and <img src="Edit_6557afba-e697-4397-994e-a9bda83e3219.png" width="19" height="20" alt="" /> are denotes the <em>k</em>-th power graphs of cycle <img src="Edit_27e6e80f-85d5-4208-b367-a757a0e55d0b.png" width="21" height="20" alt="" /> and path <img src="Edit_70ac5266-950b-4bfd-8d04-21711d3ffc33.png" width="18" height="20" alt="" />.展开更多
A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G, such that every vertex of G is dominated by at least two vertices of D. The do...A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G, such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G = （V, E）, a subset D C V（G） is a 2-dominating set if every vertex of V（G） ／ D has at least two neighbors in D, while it is a 2-outer-independent dominating set of G if additionally the set V（G）／D is independent. The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G. This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.展开更多
A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that ...A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.展开更多
Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex v∈V(G), the closed neighborhood of v contains more verti...Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex v∈V(G), the closed neighborhood of v contains more vertices with function values 1 than with −1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n.展开更多
Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination numb...Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.展开更多
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 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)=Σv∈V 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.展开更多
基金Supported by the NSF of education Department of Henan Province(200510475038)
文摘A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.
文摘This paper discusses how the infinite set of real numbers between 0 and 1 could be represented by a countably infinite tree structure which would avoid Cantor’s diagonalization argument that the set of real numbers is not countably infinite. Likewise, countably infinite tree structures could represent all real numbers, and all points in any number of dimensions in multi-dimensional spaces. The objective of this paper is not to overturn previous research based on Cantor’s argument, but to suggest that this situation may be treated as a definitional or axiomatic choice. This paper proposes a “non-Cantorian” branch of cardinality theory, representing all these infinities with countably infinite tree structures. This approach would be consistent with the Continuum Hypothesis.
文摘A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.
文摘Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Then majority domination number of a graph G is γ maj(G)=min{f(V)|f is a majority dominating function on G}. We obtain lower bounds on this parameter and generalize some results of Henning.
文摘Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of a total dominating set of G. This paper proves that if G is a connected graph with n≥3 vertices and minimum degree at least two.
基金The National Natural Science Foundation of China(No.10971025)
文摘Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.
文摘This paper studies the strong law of large numbers and the Shannom-McMillan theorem for Markov chains field on Cayley tree. The authors first prove the strong law of large number on the frequencies of states and orderd couples of states for Markov chains field on Cayley tree. Then they prove the Shannon-McMillan theorem with a.e. convergence for Markov chains field on Cayley tree. In the proof, a new technique in the study the strong limit theorem in probability theory is applied.
基金Supported by National Basic Research Program of China(973 Program No.2007CBS14903)National Science Foundation of China(70671069)
文摘Some strong laws of large numbers for the frequencies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields （NSMC） on Cayley trees are studied. In the proof, a new technique for the study of strong limit theorems of Markov chains is extended to the case of Markov chain fields, The asymptotic equipartition properties with almost everywhere （a,e.） convergence for NSMC on Cayley trees are obtained,
文摘A vertex subversion strategy of a graph G=(V,E) is a set of vertices S V(G) whose closed neighborhood is deleted from G . The survival subgraph is denoted by G/S . We call S a cut-strategy of G if G/S is disconnected, or is a clique, or is φ . The vertex-neighbor scattering number of G is defined to be VNS(G)=max{ω(G/S)-|S|} , where S is any cut-strategy of G , and ω(G/G) is the number of the components of G/S . It has been proved that the computing problem of this parameter is NP–complete, so we discuss the properties of vertex-neighbor-scattering number of trees in this paper.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571117）, and the Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.
基金The NSF(11301450,61363020,11226294)of Chinathe Youth Science and Technology Education Project(2014731003)of Xinjiang Province
文摘Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.
文摘A new combinatorial interpretation of Raney numbers is proposed. We apply this combinatorial interpretation to solve several tree enumeration counting problems. Further a generalized Catalan triangle is introduced and some of its properties are proved.
文摘The independence number of a graph G is the maximum cardinality among all independent sets of G. For any tree T of order n ≥ 2, it is easy to see that . In addition, if there are duplicated leaves in a tree, then these duplicated leaves are all lying in every maximum independent set. In this paper, we will show that if T is a tree of order n ≥ 4 without duplicated leaves, then . Moreover, we constructively characterize the extremal trees T of order n ≥ 4, which are without duplicated leaves, achieving these upper bounds.
文摘Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16fc53d.png" width="79" height="20" alt="" /> is said to be a Signed Dominating Function (SDF) if <img src="Edit_c6e63805-bcaa-46a9-bc77-42750af8efd4.png" width="135" height="25" alt="" /> holds for all <img src="Edit_bba1b366-af70-46cd-aefe-fc68869da670.png" width="42" height="20" alt="" />. The signed domination number <img src="Edit_22e6d87a-e3be-4037-b4b6-c1de6a40abb0.png" width="284" height="25" alt="" />. In this paper, we determine the exact value of the Signed Domination Number of graphs <img src="Edit_36ef2747-da44-4f9b-a10a-340c61a3f28c.png" width="19" height="20" alt="" /> and <img src="Edit_26eb0f74-fcc2-49ad-8567-492cf3115b73.png" width="19" height="20" alt="" /> for <img src="Edit_856dbcc1-d215-4144-b50c-ac8a225d664f.png" width="32" height="20" alt="" />, which is generalized the known results, respectively, where <img src="Edit_4b7e4f8f-5d38-4fd0-ac4e-dd8ef243029f.png" width="19" height="20" alt="" /> and <img src="Edit_6557afba-e697-4397-994e-a9bda83e3219.png" width="19" height="20" alt="" /> are denotes the <em>k</em>-th power graphs of cycle <img src="Edit_27e6e80f-85d5-4208-b367-a757a0e55d0b.png" width="21" height="20" alt="" /> and path <img src="Edit_70ac5266-950b-4bfd-8d04-21711d3ffc33.png" width="18" height="20" alt="" />.
文摘A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G, such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G = （V, E）, a subset D C V（G） is a 2-dominating set if every vertex of V（G） ／ D has at least two neighbors in D, while it is a 2-outer-independent dominating set of G if additionally the set V（G）／D is independent. The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G. This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.
基金the Polish Ministry of Science and Higher Education grand IP/2012/038972
文摘A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.
文摘Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex v∈V(G), the closed neighborhood of v contains more vertices with function values 1 than with −1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n.
文摘Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
文摘Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.
基金Supported by National Natural Science Foundation of China(Grant No.12171440)。
文摘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)=Σv∈V 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.
