Opuscula Math. 32, no. 3 (2012), 423-437
http://dx.doi.org/10.7494/OpMath.2012.32.3.423

Opuscula Mathematica

# 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)

• M. Atapour
• Azarbaijan University of Tarbiat Moallem, Department of Mathematics, Tabriz, I.R. Iran
• S. M. Sheikholeslami
• Azarbaijan University of Tarbiat Moallem, Department of Mathematics, Tabriz, I.R. Iran
• Abdollah Khodkar
• University of West Georgia, Department of Mathematics, Carrollton, GA 30118, USA
• Revised: 2011-09-11.
• Accepted: 2011-10-03.