MATHEMATICA BOHEMICA, Vol. 142, No. 1, pp. 9-20, 2017

Changing of the domination number of a graph: edge multisubdivision and edge removal

Vladimir Samodivkin

Received February 25, 2015.   First published October 18, 2016.

Vladimir Samodivkin, Departement of Mathematics, Faculty of Transportation Engineering, Civil Engineering and Geodesy, University of Architecture, 1 Hristo Smirnenski Blvd., 1046 Sofia, Bulgaria, e-mail:

Abstract: For a graphical property $\mathcal{P}$ and a graph $G$, a subset $S$ of vertices of $G$ is a $\mathcal{P}$-set if the subgraph induced by $S$ has the property $\mathcal{P}$. The domination number with respect to the property $\mathcal{P}$, denoted by $\gamma_{\mathcal{P}} (G)$, is the minimum cardinality of a dominating $\mathcal{P}$-set. We define the domination multisubdivision number with respect to $\mathcal{P}$, denoted by $ msd _{\mathcal{P}}(G)$, as a minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to change $\gamma_{\mathcal{P}} (G)$. In this paper \item{(a)} we present necessary and sufficient conditions for a change of $\gamma_{\mathcal{P}}(G)$ after subdividing an edge of $G$ once, \item{(b)} we prove that if $e$ is an edge of a graph $G$ then $\gamma_{\mathcal{P}} (G_{e,1}) < \gamma_{\mathcal{P}} (G)$ if and only if $\gamma_{\mathcal{P}} (G-e) < \gamma_{\mathcal{P}} (G)$ ($G_{e,t}$ denotes the graph obtained from $G$ by subdivision of $e$ with $t$ vertices), \item{(c)} we also prove that for every edge of a graph $G$ we have $\gamma_{\mathcal{P}}(G-e)\leq\gamma_{\mathcal{P}}(G_{e,3})\leq\gamma_{\mathcal{P}}(G-e) + 1$, and \item{(d)} we show that $ msd_{\mathcal{P}}(G) \leq3$, where $\mathcal{P}$ is hereditary and closed under union with $K_1$.

Keywords: dominating set; edge subdivision; domination multisubdivision number; hereditary graph property

Classification (MSC 2010): 05C69

DOI: 10.21136/MB.2017.0009-15

Full text available as PDF.

  [1] D. Avella-Alaminos, M. Dettlaff, M. Lemańska, R. Zuazua: Total domination multisubdivision number of a graph. Discuss. Math. Graph Theory 35 (2015), 315-327. DOI 10.7151/dmgt.1798 | MR 3338756 | Zbl 1311.05143
  [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin: A survey of hereditary properties of graphs. Discuss. Math., Graph Theory 17 (1997), 5-50. DOI 10.7151/dmgt.1037 | MR 1633268 | Zbl 0902.05026
  [3] E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi: Total domination in graphs. Networks 10 (1980), 211-219. DOI 10.1002/net.3230100304 | MR 0584887 | Zbl 0447.05039
  [4] E. J. Cockayne, O. Favaron, C. M. Mynhardt: On $i^-$-ER-critical graphs. 6th Int. Conf. Graph Theory. Discrete Math. 276 (2004), 111-125. DOI 10.1016/S0012-365X(03)00302-9 | MR 2046628 | Zbl 1031.05093
  [5] E. J. Cockayne, S. T. Hedetniemi: Independence graphs. Proc. 5th Southeast. Conf. Comb., Graph Theor., Comput., Boca Raton 1974 Utilitas Math., Winnipeg, Man. (1974), 471-491. MR 0357174 | Zbl 0305.05114
  [6] M. Dettlaff, J. Raczek, J. Topp: Domination subdivision and domination multisubdivision numbers of graphs. Available at
  [7] O. Favaron, H. Karami, S. M. Sheikholeslami: Connected domination subdivision numbers of graphs. Util. Math. 77 (2008), 101-111. MR 2462631 | Zbl 1161.05055
  [8] O. Favaron, H. Karami, S. M. Sheikholeslami: Paired-domination subdivision numbers of graphs. Graphs Comb. 25 (2009), 503-512. DOI 10.1007/s00373-005-0871-1 | MR 2575597 | Zbl 1216.05102
  [9] J. F. Fink, M. S. Jacobson: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science. Proc. 5th Int. Conf., Kalamazoo/Mich. 1984 John Wiley, New York (1985), 301-311. MR 0812672 | Zbl 0573.05050
  [10] W. Goddard, T. Haynes, D. Knisley: Hereditary domination and independence parameters. Discuss. Math., Graph Theory 24 (2004), 239-248. DOI 10.7151/dmgt.1228 | MR 2120566 | Zbl 1065.05069
  [11] P. J. P. Grobler: Critical Concepts in Domination, Independence and Irredundance of Graphs. Ph.D. Thesis, University of South Africa, ProQuest LLC (1999). MR 2716892
  [12] P. J. P. Grobler, C. M. Mynhardt: Upper domination parameters and edge-critical graphs. J. Comb. Math. Comb. Comput. 33 (2000), 239-251. MR 1772765 | Zbl 0959.05084
  [13] P. J. P. Grobler, C. M. Mynhardt: Domination parameters and edge-removal-critical graphs. Discrete Math. 231 (2001), 221-239. DOI 10.1016/S0012-365X(00)00319-8 | MR 1821961 | Zbl 0973.05056
  [14] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Pure and Applied Mathematics 208 Marcel Dekker, New York (1998). MR 1605684 | Zbl 0890.05002
  [15] T. W. Haynes, M. A. Henning, L. S. Hopkins: Total domination subdivision numbers of graphs. Discuss. Math., Graph Theory 24 (2004), 457-467. DOI 10.7151/dmgt.1244 | MR 2120069 | Zbl 1065.05070
  [16] T. W. Haynes, P. J. Slater: Paired-domination in graphs. Networks 32 (1998), 199-206. DOI 10.1002/(SICI)1097-0037(199810)32:3 | MR 1645415 | Zbl 0997.05074
  [17] S. M. Hedetniemi, S. T. Hedetniemi, D. F. Rall: Acyclic domination. Discrete Math. 222 (2000), 151-165. DOI 10.1016/S0012-365X(00)00012-1 | MR 1771395 | Zbl 0961.05052
  [18] M. Lemańska, J. Tey, R. Zuazua: Relations between edge removing and edge subdivision concerning domination number of a graph. Available at
  [19] D. Michalak: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141-146. DOI 10.1016/j.disc.2003.11.054 | MR 2084289 | Zbl 1051.05069
  [20] V. Samodivkin: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. MR 2428312 | Zbl 1199.05269
  [21] V. Samodivkin: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. MR 2554536 | Zbl 1207.05145
  [22] V. Samodivkin: Domination with respect to nondegenerate properties: vertex and edge removal. Math. Bohem. 138 (2013), 75-85. MR 3076222 | Zbl 1274.05363
  [23] V. Samodivkin: Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces. Czech. Math. J. 63 (2013), 191-204. DOI 10.1007/s10587-013-0013-5 | MR 3035506 | Zbl 1274.05364
  [24] E. Sampathkumar, H. B. Walikar: The connected domination of a graph. J. Math. Phys. Sci. 13 (1979), 607-613. Zbl 0449.05057
  [25] S. Velammal: Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University (1997).

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at

[Previous Article] [Next Article] [Contents of This Number] [Contents of Mathematica Bohemica] [Full text of the older issues of Mathematica Bohemica at DML-CZ]