Disjunctive Total Domination Subdivision Number of Graphs

• Autorzy: Çiftçi Canan , Aytaç Vecdi

Identyfikatory

DOI

10.3233/FI-2020-1928

• Języki publikacji: EN

Abstrakty

EN

A set S ⊆ V (G) is a disjunctive total dominating set of G if every vertex has a neighbor in S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number is the minimum cardinality of a disjunctive total dominating set in G. We define the disjunctive total domination subdivision number of G as the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) to increase the disjunctive total domination number. In this paper, we first study the disjunctive total domination subdivision number of some special graphs. Next, we give some upper bounds on the disjunctive total domination subdivision number for any graphs in terms of vertex degree. Finally, we supply some conditions for a graph G to have a minimum disjunctive total domination subdivision number.

Słowa kluczowe

EN

disjunctive total domination; domination; subdivision

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 1
• Strony: 15--26
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Çiftçi Canan

• Department of Mathematics, Faculty of Arts and Sciences, Ordu University, 52200, Ordu, Turkey

autor

Aytaç Vecdi

• Department of Computer Engineering, Faculty of Engineering, Ege University, 35100, Izmir, Turkey

Bibliografia

• [1] Haynes TW, Hedetniemi S, Slater P. Fundamentals of domination in graphs. Marcel Dekker, Inc, 1998.
• [2] Henning MA, Naicker V. Disjunctive total domination in graphs. Journal of Combinatorial Optimization, 2016. 31(3):1090-1110. doi:10.1007/s10878-014-9811-4.
• [3] Naicker V, Henning MA. Graphs with large disjunctive total domination number. Discrete Mathematics & Theoretical Computer Science, 2015. 17(1):255-281. URL https://hal.inria.fr/hal-01196847.
• [4] Henning MA, Naicker V. Bounds on the disjunctive total domination number of a tree. Discussiones Mathematicae Graph Theory, 2016. 36(1):153-171. doi:10.7151/dmgt.1854.
• [5] Lin CF, Peng SL, Yang HD. Disjunctive total domination numbers of grid graphs. In: 2016 International Computer Symposium (ICS). IEEE, 2016 pp. 80-83. doi:10.1109/ICS.2016.0024.
• [6] Yi E. Disjunctive total domination in permutation graphs. Discrete Mathematics, Algorithms and Applications, 2017. 9(01):1750009. doi:10.1142/S1793830917500094.
• [7] Çiftçi C, Aytaç V. Disjunctive total domination in Harary graphs. submitted.
• [8] Çiftçi C, Aytaç A. Disjunctive total domination on the corona and join of graphs. submitted.
• [9] Bauer D, Harary F, Nieminen J, Suffel CL. Domination alteration sets in graphs. Discrete Mathematics, 1983. 47:153-161. doi:10.1016/0012-365X(83)90085-7.
• [10] Fink JF, Jacobson MS, Kinch LF, Roberts J. The bondage number of a graph. Discrete Mathematics, 1990. 86(1-3):47-57. doi:10.1016/0012-365X(90)90348-L.
• [11] Kok J, Mynhardt C. Reinforcement in graphs. Congr. Numer, 1990. 79:225-231.
• [12] Velammal S. Studies in graph theory: covering, independence, domination and related topics. Ph.D. thesis, Manonmaniam Sundaranar University Tirunelveli, 1997.
• [13] Haynes T, Hedetniemi SM, Hedetniemi ST. Domination and independence subdivision numbers of graphs. Discussiones Mathematicae Graph Theory, 2000. 20(2):271-280. doi:10.7151/dmgt.1126.
• [14] Haynes T, Hedetniemi SM, Hedetniemi ST, Jacobs D, Knisely J, Van Der Merwe L. Domination subdivision numbers. Discussiones Mathematicae Graph Theory, 2001. 21(2):239-253. doi:10.7151/dmgt.1147.
• [15] Karami H, Sheikholeslami SM. Trees whose domination subdivision number is one. Australasian Journal of Combinatorics, 2008. 40:161-166.
• [16] Favaron O, Haynes TW, Hedetniemi ST. Domination subdivision numbers in graphs. Utilitas Mathematica, 2004. 66:195-209.
• [17] Aram H, Sheikholeslami SM, Favaron O. Domination subdivision numbers of trees. Discrete Mathematics, 2009. 309(4):622-628. doi:10.1016/j.disc.2007.12.085.
• [18] Sharada B, Soner ND. On the domination subdivision numbers of trees. Australasian J. Combinatorics, 2010. 46:233-240.
• [19] Haynes T, Hedetniemi ST, Van Der Merwe L. Total domination subdivision numbers. Journal of Combinatorial Mathematics and Combinatorial Computting, 2003. 44:115-128.
• [20] Hopkins LS. Bounds on total domination subdivision numbers. Electronic Theses and Dissertations, 2003. URL http://dc.etsu.edu/etd/738.
• [21] Haynes T, Henning M, Hopkins L. Total domination subdivision numbers of graphs. Discussiones Mathematicae Graph Theory, 2004. 24(3):457-467. doi:10.7151/dmgt.1244.
• [22] Haynes TW, Henning MA, Hopkins L. Total domination subdivision numbers of trees. Discrete mathematics, 2004. 286(3):195-202. doi:10.1016/j.disc.2004.06.004.
• [23] Karami H, Khoeilar R, Sheikholeslami SM, Khodkar A. An upper bound for the total domination subdivision number of a graph. Graphs and Combinatorics, 2009. 25(5):727-733. doi:10.1007/s00373-010-0877-1.
• [24] Favaron O, Karami H, Khoeilar R, Sheikholeslami SM. On the total domination subdivision number in some classes of graphs. Journal of Combinatorial Optimization, 2010. 20(1):76-84. doi:10.1007/s10878-008-9193-6.
• [25] Favaron O, Karami H, Sheikholeslami SM. Bounding the total domination subdivision number of a graph in terms of its order. Journal of Combinatorial Optimization, 2011. 21(2):209-218. doi:10.1007/s10878-009-9224-y.
• [26] Favaron O, Karami H, Sheikholeslami SM. Paired-domination subdivision numbers of graphs. Graphs and Combinatorics, 2009. 25(4):503-512. doi:10.1007/s00373-005-0871-1.
• [27] Atapour M, Sheikholeslami SM, Hansberg A, Volkmann L, Khodkar A. 2-domination subdivision number of graphs. AKCE J.Graphs.Combin, 2008. 5:165-173.
• [28] Atapour M, Khodkar A, Sheikholeslami SM. Characterization of double domination subdivision number of trees. Discrete Applied Mathematics, 2007. 155(13):1700-1707. doi:10.1016/j.dam.2007.03.007.
• [29] Dettlaff M, Kosary S, Lemańska M, Sheikholeslami SM. Weakly convex domination subdivision number of a graph. Filomat, 2016. 30(8):2101-2110. doi:10.2298/FIL1608101D.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).