A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families of graphs. Then we show that the total domination subdivision number of a graph can be arbitrarily large.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1244,
author = {Teresa W. Haynes and Michael A. Henning and Lora S. Hopkins},
title = {Total domination subdivision numbers of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {457-467},
zbl = {1065.05070},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1244}
}
Teresa W. Haynes; Michael A. Henning; Lora S. Hopkins. Total domination subdivision numbers of graphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 457-467. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1244/
[000] [1] S. Arumugam, private communication, June, 2000.
[001] [2] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. | Zbl 0447.05039
[002] [3] O. Favaron, T.W. Haynes, and S.T. Hedetniemi, Domination subdivision numbers in graphs, submitted for publication. | Zbl 1071.05057
[003] [4] 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. | Zbl 0984.05066
[004] [5] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, and L.C. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001) 239-253, doi: 10.7151/dmgt.1147. | Zbl 1006.05042
[005] [6] T.W. Haynes, M.A. Henning, and L.S. Hopkins, Total domination subdivision numbers in trees, submitted for publication. | Zbl 1054.05076
[006] [7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[007] [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). | Zbl 0883.00011
[008] [9] T.W. Haynes, S.T. Hedetniemi, and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003) 115-128. | Zbl 1020.05048