Total Domination Multisubdivision Number of a Graph

Diana Avella-Alaminos; Magda Dettlaff; Magdalena Lemańska; Rita Zuazua

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 315-327
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Diana Avella-Alaminos, et al. "Total Domination Multisubdivision Number of a Graph." Discussiones Mathematicae Graph Theory 35.2 (2015): 315-327. <http://eudml.org/doc/271098>.

@article{DianaAvella2015,
abstract = {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.},
author = {Diana Avella-Alaminos, Magda Dettlaff, Magdalena Lemańska, Rita Zuazua},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {(total) domination; (total) domination subdivision number; (total) domination multisubdivision number; trees; total domination; total domination subdivision number; total domination multisubdivision number},
language = {eng},
number = {2},
pages = {315-327},
title = {Total Domination Multisubdivision Number of a Graph},
url = {http://eudml.org/doc/271098},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Diana Avella-Alaminos
AU - Magda Dettlaff
AU - Magdalena Lemańska
AU - Rita Zuazua
TI - Total Domination Multisubdivision Number of a Graph
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 315
EP - 327
AB - 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.
LA - eng
KW - (total) domination; (total) domination subdivision number; (total) domination multisubdivision number; trees; total domination; total domination subdivision number; total domination multisubdivision number
UR - http://eudml.org/doc/271098
ER -

References

top
  1. [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] Zbl1171.05380
  2. [2] S. Benecke and C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008) 201-209. Zbl1153.05018
  3. [3] M. Dettlaff, J. Raczek and J. Topp, Domination subdivision and multisubdivision numbers of graphs, submitted. 
  4. [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] Zbl1193.05124
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998). Zbl0890.05002
  6. [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. Zbl1020.05048
  7. [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. [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. [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. Zbl1168.05050
  10. [10] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997). 

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.