Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (2): 485-494.doi: 10.1007/s40305-022-00428-2

Previous Articles     Next Articles

2-Independent Domination in Trees

Gang Zhang, Baoyindureng Wu   

  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, Xinjiang, China
  • Received:2020-11-21 Revised:2022-06-01 Online:2024-06-30 Published:2024-06-12
  • Contact: Baoyindureng Wu, Gang Zhang E-mail:baoywu@163.com;gzh_ang@163.com
  • Supported by:
    This research is supported by the National Natural Science Foundation of China (No. 12061073).

Abstract: A subset DV (G) in a graph G is a dominating set if every vertex in V (G) \ D is adjacent to at least one vertex of S. A subset SV (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 DV (G) in a graph G is a 2-independent dominating set if D is both dominating and 2-independent. The 2-independent domination number i2(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 i2(T) = n/2. Moreover, we prove that for any tree T of order n≥2, i2(T)≤2/3α2(T), and this bound is sharp.

Key words: Domination, Independent domination, 2-Independent domination, 2-Independence, Trees

CLC Number: