Opuscula Math. 36, no. 5 (2016), 575-588
http://dx.doi.org/10.7494/OpMath.2016.36.5.575
Opuscula Mathematica
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
Magda Dettlaff
Joanna Raczek
Ismael G. Yero
Abstract. Given a graph \(G=(V,E)\), the subdivision of an edge \(e=uv\in 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 defined similarly. In this paper we study the domination, paired domination and independent domination (subdivision and multisubdivision) numbers of the generalized corona graphs.
Keywords: domination, paired domination, independent domination, edge subdivision, edge multisubdivision, corona graph.
Mathematics Subject Classification: 05C69, 05C70, 05C76.
- H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622-628.
- S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Combin. 42 (2008), 201-209.
- A. Bhattacharya, G.R. Vijayakumar, Effect of edge-subdivision on vertex-domination in a graph, Discuss. Math. Graph Theory 22 (2002), 335-347.
- M. Dettlaff, J. Raczek, J. Topp, Domination subdivision and domination multisubdivision numbers of graphs, arXiv:1310.1345 [math.CO], submitted.
- O. Favaron, T.W. Haynes, S.T. Hedetniemi, Domination subdivision numbers in graphs, Util. Math. 66 (2004), 195-209.
- 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.
- 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.
- I. González Yero, D. Kuziak, A. Rondón Aguilar, Coloring, location and domination of corona graphs, Aequationes Math. 86 (2013), 1-21.
- T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-206.
- T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000), 271-280.
- 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.
- T.W. Haynes, S.T. Hedetniemi, L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003), 115-128.
- C. Payan, N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 1, 23-32.
- J. Raczek, M. Dettlaff, Paired domination subdivision and multisubdivision numbers of graphs, submitted.
- S. Velammal, Studies in graph theory: covering, independence, domination and related topics, Ph.D. Thesis, Manonmaniam Sundaranar University, Tirunelveli, 1997.
- Magda Dettlaff
- Gdańsk University of Technology, Faculty of Applied Physics and Mathematics, ul. Narutowicza 11/12, 80-233 Gdańsk, Poland
- Joanna Raczek
- Gdańsk University of Technology, Faculty of Applied Physics and Mathematics, ul. Narutowicza 11/12, 80-233 Gdańsk, Poland
- Ismael G. Yero
- Universidad de Cádiz, Escuela Politécnica Superior de Algeciras, Departamento de Matemáticas, Av. Ramón Puyol, s/n, 11202 Algeciras, Spain
- Communicated by Dalibor Fronček.
- Received: 2015-12-02.
- Revised: 2016-05-08.
- Accepted: 2016-05-10.
- Published online: 2016-06-29.
