2-Independent Domination in Trees  

作　　者：Gang Zhang Baoyindureng Wu 

机构地区：[1]College of Mathematics and System Sciences,Xinjiang University,Urumqi,830046,Xinjiang,China

出　　处：《Journal of the Operations Research Society of China》2024年第2期485-494,共10页中国运筹学会会刊（英文）

基　　金：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.

关 键 词：DOMINATION Independent domination 2-Independent domination 2-Independence Trees 

分 类 号：O15[理学—数学]