Abstract
A set S of vertices in a graph G is a 2-dominating set of G if every vertex not in S has at least two neighbors in S, where two vertices are neighbors if they are adjacent. The 2-domination number of G, denoted by γ 2 (G), is the minimum cardinality among all 2-dominating sets in G. A γ 2-set of G is a 2-dominating set of G of cardinality γ 2 (G). The 2-domination subdivision number of G, denoted by sd 2 (G), is the minimum number of ISSN: 2202-3518 c The author(s). Released under the CC BY 4.0 International License M. DETTLAFF ET AL. / AUSTRALAS. J. COMBIN. 93 (1) (2025), 150–170 151 edges which must be subdivided in order to increase the 2-domination number. If T is a tree of order n ≥ 3, then sd 2 (T) ≤ 2. We show that sd 2 (T) = 1 if and only if the set of vertices that belong to no γ 2-set of G is nonempty. A graph G is γ 2-q-critical if q is the least number such that for every subset of edges S of cardinality q, the graph produced by subdivision of S has a greater 2-domination number. If T is a γ 2-q-critical tree of order n ≥ 3, then we prove that q ≤ n − 2. Among other results, we characterize γ 2-q-critical trees when q is large, namely q ∈ {n − 4, n − 3, n − 2}. We also characterize γ 2-1-critical trees.