Geodesic
Domination Subdivision and Domination Multisubdivision Numbers of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 829-839.

Voir la notice de l'article provenant de la source Library of Science

The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T) ≤ 3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number of a nonempty graph G as a minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. We show that msd(G) ≤ 3 for any graph G. The domination subdivision number and the domination multisubdivision number of a graph are incomparable in general, but we show that for trees these two parameters are equal. We also determine the domination multisubdivision number for some classes of graphs.
Keywords: domination, domination subdivision number, domination multisubdivision number, trees, computational complexity 
@article{DMGT_2019_39_4_a4,
     author = {Dettlaff, Magda and Raczek, Joanna and Topp, Jerzy},
     title = {Domination {Subdivision} and {Domination} {Multisubdivision} {Numbers} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {829--839},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a4/}
}
TY  - JOUR
AU  - Dettlaff, Magda
AU  - Raczek, Joanna
AU  - Topp, Jerzy
TI  - Domination Subdivision and Domination Multisubdivision Numbers of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 829
EP  - 839
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a4/
LA  - en
ID  - DMGT_2019_39_4_a4
ER  - 
%0 Journal Article
%A Dettlaff, Magda
%A Raczek, Joanna
%A Topp, Jerzy
%T Domination Subdivision and Domination Multisubdivision Numbers of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 829-839
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a4/
%G en
%F DMGT_2019_39_4_a4
Dettlaff, Magda; Raczek, Joanna; Topp, Jerzy. Domination Subdivision and Domination Multisubdivision Numbers of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 829-839. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a4/

[1] H. Aram, S.M. Sheikholeslami and O. Favaron, Domination subdivision numbers of trees, Discrete Math. 309 (2009) 622–628. doi:10.1016/j.disc.2007.12.085

[2] D. Avella-Alaminos, M. Dettlaff, M. Lemańska and R. Zuazua, Total domination multisubdivision number of a graph, Discuss. Math. Graph Theory 35 (2015) 315–327. doi:10.7151/dmgt.1798

[3] S. Benecke and C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008) 201–209.

[4] A. Bhattacharya and G.R. Vijayakumar, Effect of edge-subdivision on vertex-domination in a graph, Discuss. Math. Graph Theory 22 (2002) 335–347. doi:10.7151/dmgt.1179

[5] O. Favaron, T.W. Haynes and S.T. Hedetniemi, Domination subdivision numbers in graphs, Util. Math. 66 (2004) 195–209.

[6] O. Favaron, H. Karami and S.M. Sheikholeslami, Disproof of a conjecture on the subdivision domination number of a graph, Graphs Combin. 24 (2008) 309–312. doi:10.1007/s00373-008-0788-6

[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

[8] T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000) 271–280. doi:10.7151/dmgt.1126

[9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).

[10] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D.Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).