A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set ...A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].展开更多
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.展开更多
A subset S V in a graph G =（V, E） is a total [1, 2]-set if, for every vertex v ∈ V, 1 ≤ ｜N（v）∩S｜ ≤2. The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted...A subset S V in a graph G =（V, E） is a total [1, 2]-set if, for every vertex v ∈ V, 1 ≤ ｜N（v）∩S｜ ≤2. The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted byγt[1,2]（G）.We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover,we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total[1, 2]-domination number, [1, 2]-domination number and domination number.展开更多
文摘A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].
基金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.
基金Supported by the National Natural Science Foundation of China(No.11001269,No.11571294)
文摘A subset S V in a graph G =（V, E） is a total [1, 2]-set if, for every vertex v ∈ V, 1 ≤ ｜N（v）∩S｜ ≤2. The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted byγt[1,2]（G）.We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover,we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total[1, 2]-domination number, [1, 2]-domination number and domination number.
