A subset D■V(G)in a graph G is a dominating set if every vertex in V(G)I D is adjacent to at least one vertex of S.A subset S■V(G)in a graph G is a 2-independent set if△(G[S])<2.The 2-independence numberα2(G)is...A subset D■V(G)in a graph G is a dominating set if every vertex in V(G)I D is adjacent to at least one vertex of S.A subset S■V(G)in a graph G is a 2-independent set if△(G[S])<2.The 2-independence numberα2(G)is the order of a largest 2-independent set in G.Further,a subset D■V(G)in a graph G is a 2-independent dominating set if D is both dominating and 2-independent.The 2-independent domination number i^(2)(G)is the order of a smallest 2-independent dominating set in G.In this paper,we characterize all trees T of order n with i^(2)(T)=n/2.Moreover,we prove that for any tree T of order n≥2,i^(2)(T)≤2/3α2(T),and this bound is sharp.展开更多
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.展开更多
基金the National Natural Science Foundation of China(No.12061073).
文摘A subset D■V(G)in a graph G is a dominating set if every vertex in V(G)I D is adjacent to at least one vertex of S.A subset S■V(G)in a graph G is a 2-independent set if△(G[S])<2.The 2-independence numberα2(G)is the order of a largest 2-independent set in G.Further,a subset D■V(G)in a graph G is a 2-independent dominating set if D is both dominating and 2-independent.The 2-independent domination number i^(2)(G)is the order of a smallest 2-independent dominating set in G.In this paper,we characterize all trees T of order n with i^(2)(T)=n/2.Moreover,we prove that for any tree T of order n≥2,i^(2)(T)≤2/3α2(T),and this bound is sharp.
基金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.
