Total domination subdivision numbers of graphs

Teresa W. Haynes; Michael A. Henning; Lora S. Hopkins

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 457-467
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Teresa W. Haynes, Michael A. Henning, and Lora S. Hopkins. "Total domination subdivision numbers of graphs." Discussiones Mathematicae Graph Theory 24.3 (2004): 457-467. <http://eudml.org/doc/270656>.

@article{TeresaW2004,
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.},
author = {Teresa W. Haynes, Michael A. Henning, Lora S. Hopkins},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total domination number; total domination subdivision number},
language = {eng},
number = {3},
pages = {457-467},
title = {Total domination subdivision numbers of graphs},
url = {http://eudml.org/doc/270656},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Teresa W. Haynes
AU - Michael A. Henning
AU - Lora S. Hopkins
TI - Total domination subdivision numbers of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 457
EP - 467
AB - 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.
LA - eng
KW - total domination number; total domination subdivision number
UR - http://eudml.org/doc/270656
ER -

References

top
  1. [1] S. Arumugam, private communication, June, 2000. 
  2. [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. Zbl0447.05039
  3. [3] O. Favaron, T.W. Haynes, and S.T. Hedetniemi, Domination subdivision numbers in graphs, submitted for publication. Zbl1071.05057
  4. [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. Zbl0984.05066
  5. [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. Zbl1006.05042
  6. [6] T.W. Haynes, M.A. Henning, and L.S. Hopkins, Total domination subdivision numbers in trees, submitted for publication. Zbl1054.05076
  7. [7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  8. [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  9. [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. Zbl1020.05048

Citations in EuDML Documents

top
  1. Seyed Sheikholeslami, On the total domination subdivision numbers in graphs
  2. Diana Avella-Alaminos, Magda Dettlaff, Magdalena Lemańska, Rita Zuazua, Total Domination Multisubdivision Number of a Graph
  3. Joanna Raczek, Weakly connected domination subdivision numbers
  4. Odile Favaron, Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami, Matchings and total domination subdivision number in graphs with few induced 4-cycles
  5. Vladimir D. Samodivkin, Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces
  6. Vladimir D. Samodivkin, Changing of the domination number of a graph: edge multisubdivision and edge removal

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.