Total Domination Multisubdivision Number of a Graph

• Autorzy: Diana Avella-Alaminos , Magda Dettlaff , Magdalena Lemańska , Rita Zuazua
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

(total) domination; (total) domination subdivision number; (total) domination multisubdivision number; trees

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 315-327

Daty

wydano

2015-05-01

otrzymano

2014-01-13

poprawiono

2014-08-16

zaakceptowano

2014-08-16

online

2015-04-18

Twórcy

autor

Diana Avella-Alaminos

• Universidad Nacional Autónoma de México, Mexico

autor

Magda Dettlaff

• Gdańsk University of Technology, Poland

autor

Magdalena Lemańska

• Gdańsk University of Technology, Poland

autor

Rita Zuazua

• Universidad Nacional Autónoma de México, Mexico

Bibliografia

• [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]
• [2] S. Benecke and C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008) 201-209.
• [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]
• [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
• [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.
• [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.
• [10] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).

Identyfikatory

DOI

10.7151/dmgt.1798