Feb MAR SEP » 4 2016 2017 2018 2 captures 4 Mar 17 - 2 Sep 17

Close Help

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

Vladimir Samodivkin

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

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.

References:
  [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 http://arxiv.org/pdf/1310.1345v2.pdf.
  [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 http://arxiv.org/abs/1409.7508.
  [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).