Trees whose 2-domination subdivision number is 2
Author(s) -
Maryam Atapour,
Seyed Mahmoud Sheikholeslami,
Abdollah Khodkar
Publication year - 2012
Publication title -
opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2012.32.3.423
Subject(s) - mathematics , combinatorics , subdivision , vertex (graph theory) , dominating set , domination analysis , graph , constructive , discrete mathematics , computer science , archaeology , process (computing) , history , operating system
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\)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom