Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs

• Autorzy: Dettlaff M. , Raczek J. , Yero I. G.

Identyfikatory

DOI

10.7494/OpMath.2016.36.5.575

• Języki publikacji: EN

Abstrakty

EN

Given a graph G = (V, E), the subdivision of an edge e = uv ∈ E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions which must be done in one edge such that the domination number increases. Moreover, the concepts of paired domination and independent domination subdivision (respectively multisubdivision) numbers are denned similarly. In this paper we study the domination, paired domination and independent domination (subdivision and multisubdivision) numbers of the generalized corona graphs.

Słowa kluczowe

EN

domination; paired domination; independent domination; edge subdivision; edge multisubdivision; corona graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2016
• Tom: Vol. 36, no. 5
• Strony: 575--588
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Dettlaff M.

• Gdańsk University of Technology Faculty of Applied Physics and Mathematics ul. Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Raczek J.

• Gdańsk University of Technology Faculty of Applied Physics and Mathematics ul. Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Yero I. G.

• Universidad de Cadiz, Escuela Politecnica Superior de Algeciras Departamento de Matematicas Av. Ramón Puyol, s/n, 11202 Algeciras, Spain

Bibliografia

• [1] H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622-628.
• [2] S. Benecke, CM. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008), 201-209.
• [3] A. Bhattacharya, G.R. Vijayakumar, Effect of edge-subdivision on vertex-domination in a graph, Discuss. Math. Graph Theory 22 (2002), 335-347.
• [4] M. Dettlaff, J. Raczek, J. Topp, Domination subdivision and domination multisubdivision numbers of graphs, arXiv:1310.1345 [math.CO], submitted.
• [5] O. Favaron, T.W. Haynes, S.T. Hedetniemi, Domination subdivision numbers in graphs, Util. Math. 66 (2004), 195-209.
• [6] O. Favaron, H. Karami, S.M. Sheikholeslami, Disproof of a conjecture on the subdivision domination number of a graph, Graphs Combin. 24 (2008), 309-312.
• [7] J.F. Fink, M.S. Jacobson, L.F. Kinch, J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 4, 287-293.
• [8] I. Gonzalez Yero, D. Kuziak, A. Rondón Aguilar, Coloring, location and domination of corona graphs, Aequationes Math. 86 (2013), 1-21.
• [9] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-206.
• [10] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000), 271-280.
• [11] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, L.C. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001), 239-253.
• [12] T.W. Haynes, S.T. Hedetniemi, L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003), 115-128.
• [13] C. Payan, N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 1, 23-32.
• [14] J. Raczek, M. Dettlaff, Paired domination subdivision and multisubdivision numbers of graphs, submitted.
• [15] S. Velammal, Studies in graph theory: covering, independence, domination and related topics, Ph.D. Thesis, Manonmaniam Sundaranar University, Tirunelveli, 1997.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.