DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(3) (2004) 457-467
DOI: 10.7151/dmgt.1244

TOTAL DOMINATION SUBDIVISION NUMBERS OF GRAPHS

Teresa W. Haynes

Department of Mathematics
East Tennessee State University
Johnson City, TN 37614-0002 USA

Michael A. Henning

School of Mathematics, Statistics and
Information Technology, University of Natal
Pietermaritzburg, 3209 South Africa

Lora S. Hopkins

Department of Mathematics
East Tennessee State University
Johnson City, TN 37614-0002 USA

Abstract

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.

Keywords: total domination number, total domination subdivision number.

2000 Mathematics Subject Classification: 05C69.

References

[1] S. Arumugam, private communication, June, 2000.
[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.
[3] O. Favaron, T.W. Haynes, and S.T. Hedetniemi, Domination subdivision numbers in graphs, submitted for publication.
[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.
[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.
[6] T.W. Haynes, M.A. Henning, and L.S. Hopkins, Total domination subdivision numbers in trees, submitted for publication.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
[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.

Received 2 June 2003
Revised 29 September 2003