Trees whose 2-domination subdivision number is 2

Abstract

A set S of vertices in a graph $G=(V,E)$ is a $2$-dominating set if every vertex of $V\setminus S$ is adjacent to at least two vertices of $S$. The $2$-domination number of a graph $G$, denoted by $\gamma_2(G)$, is the minimum size of a $2$-dominating set of $G$. The $2$-domination subdivision number $sd_{\gamma_2}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the $2$-domination number. The authors have recently proved that for any tree $T$ of order at least $3$, $1 \leq sd_{\gamma_2}(T)\leq 2$. In this paper we provide a constructive characterization of the trees whose $2$-domination subdivision number is $2$.