Trees whose 2-domination subdivision number is 2

M. Atapour
S. M. Sheikholeslami
Abdollah Khodkar

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\).

Keywords: \(2\)-dominating set, \(2\)-domination number, \(2\)-domination subdivision number.

Mathematics Subject Classification: 05C69.

Full text (pdf)