The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msdγt (G) of a graph G and we show that for any connected graph G of order at least two, msdγt (G) ≤ 3. We show that for trees the total domination multisubdi- vision number is equal to the known total domination subdivision number. We also determine the total domination multisubdivision number for some classes of graphs and characterize trees T with msdγt (T) = 1.
@article{bwmeta1.element.doi-10_7151_dmgt_1798,
author = {Diana Avella-Alaminos and Magda Dettlaff and Magdalena Lema\'nska and Rita Zuazua},
title = {Total Domination Multisubdivision Number of a Graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {315-327},
zbl = {1311.05143},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1798}
}
Diana Avella-Alaminos; Magda Dettlaff; Magdalena Lemańska; Rita Zuazua. Total Domination Multisubdivision Number of a Graph. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 315-327. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1798/
[1] H. Aram, S.M. Sheikholeslami and O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009) 622-628. doi:10.1016/j.disc.2007.12.085[Crossref] | Zbl 1171.05380
[2] S. Benecke and C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008) 201-209. | Zbl 1153.05018
[3] M. Dettlaff, J. Raczek and J. Topp, Domination subdivision and multisubdivision numbers of graphs, submitted.
[4] 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[Crossref] | Zbl 1193.05124
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998). | Zbl 0890.05002
[6] T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivi- sion numbers, J. Combin. Math. Combin. Comput. 44 (2003) 115-128. | Zbl 1020.05048
[7] T.W. Haynes, M.A. Henning and L.S. Hopkins, Total domination subdivision num- bers of graphs, Discuss. Math. Graph Theory 24 (2004) 457-467. doi:10.7151/dmgt.1244[Crossref]
[8] T.W. Haynes, M.A. Henning and L.S. Hopkins, Total domination subdivision num- bers of trees, Discrete Math. 286 (2004) 195-202. doi:10.1016/j.disc.2004.06.004[Crossref]
[9] H. Karami, A. Khodkar, R. Khoeilar and S.M. Sheikholeslami, Trees whose total domination subdivision number is one, Bull. Inst. Combin. Appl. 53 (2008) 56-57. | Zbl 1168.05050
[10] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).