Trees whose 2-domination subdivision number is 2

• Autorzy: Atapour M. , Sheikholeslami S. M. , Khodkar A.
• Języki publikacji: EN

Abstrakty

EN

A set S of vertices in a graph G = (V,E) is a 2-dominating set if every vertex of V \ S is adjacent to at least two vertices of S. The 2-domination number of a graph G, denoted by γ2(G), is the minimum size of a 2-dominating set of G. The 2-domination subdivision number sdγ2 (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the 2-domination number. The authors have recently proved that for any tree T of order at least 3, 1 ≤ sdγ2 (T ) ≤ 2. In this paper we provide a constructive characterization of the trees whose 2-domination subdivision number is 2.

Słowa kluczowe

EN

2-dominating set; 2-domination number; 2-domination subdivision numbe

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 3
• Strony: 423--437
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Atapour M.

autor

Sheikholeslami S. M.

autor

Khodkar A.

• Azarbaijan University of Tarbiat Moallem, Department of Mathematics, Tabriz, I.R. Iran

Bibliografia

• [1] H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision numbers of trees, Discrete Math. 309 (2009), 622–628.
• [2] M. Atapour, A. Khodkar, S.M. Sheikholeslami, Characterization of double domination subdivision number of trees, Discrete Appl. Math. 155 (2007), 1700–1707.
• [3] M. Atapour, S.M. Sheikholeslami, A. Khodkar, Trees whose Roman domination subdivision number is 2, Util. Math. 82 (2010), 227–240.
• [4] M. Atapour, S.M. Sheikholeslami, A. Hansberg, L. Volkmann, A. Khodkar, 2-domination subdivision number of graphs, AKCE J. Graphs Combin. 5 (2008), 169–177.
• [5] M. Blidia, M. Chellali, T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Math. 306 (2006), 1840–1845.
• [6] M. Blidia, M. Chellali, L. Volkmann, Bounds on the 2-domination number of graphs,Util. Math. 71 (2006), 209–216.
• [7] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math. 26 (2006), 5–12.
• [8] P. Dankelmann, J.H. Hattingh, M.A. Henning, H.C. Swart, Trees with equal domination and restrained domination numbers, J. Global Optim. 34 (2006), 597–607.
• [9] M. Dorflinga, W. Goddard, M.A. Henning, C.M. Mynhardt, Construction of trees and graphs with equal domination parameters, Discrete Math. 306 (2006), 2647–2654.
• [10] T.W. Haynes, M.A. Henning, A characterization of i-excellent trees, Discrete Math. 248 (2002), 69–77.
• [11] T.W. Haynes,M.A. Henning, L. Hopkins, Total domination subdivision numbers of trees, Discrete Math. 286 (2004), 195–202.
• [12] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
• [13] A. Hansberg, L. Volkmann, On graphs with equal domination and 2-domination numbers, Discrete Math. 308 (2008), 2277–2281.
• [14] H. Karami, A. Khodkar, S.M. Sheikholeslami, Trees whose double domination number is twice their domination number, Congr. Numer. 186 (2007), 49–56.
• [15] R.S. Shaheen, Bounds for the 2-domination number of toroidal grid graphs, Int. J. Com- put. Math. 86 (2009), 584–588.
• [16] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc., 2000.