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

Vladimir D. Samodivkin

Mathematica Bohemica (2017)

  • Volume: 142, Issue: 1, page 9-20
  • ISSN: 0862-7959

Abstract

top
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 ${\rm 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 ${\rm msd}_{\mathcal {P}}(G) \leq 3$, where $\mathcal {P}$ is hereditary and closed under union with $K_1$.

How to cite

top

Samodivkin, Vladimir D.. "Changing of the domination number of a graph: edge multisubdivision and edge removal." Mathematica Bohemica 142.1 (2017): 9-20. <http://eudml.org/doc/287914>.

@article{Samodivkin2017,
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 $\{\rm 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 $\{\rm msd\}_\{\mathcal \{P\}\}(G) \leq 3$, where $\mathcal \{P\}$ is hereditary and closed under union with $K_1$.},
author = {Samodivkin, Vladimir D.},
journal = {Mathematica Bohemica},
language = {eng},
number = {1},
pages = {9-20},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Changing of the domination number of a graph: edge multisubdivision and edge removal},
url = {http://eudml.org/doc/287914},
volume = {142},
year = {2017},
}

TY - JOUR
AU - Samodivkin, Vladimir D.
TI - Changing of the domination number of a graph: edge multisubdivision and edge removal
JO - Mathematica Bohemica
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 142
IS - 1
SP - 9
EP - 20
AB - 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 ${\rm 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 ${\rm msd}_{\mathcal {P}}(G) \leq 3$, where $\mathcal {P}$ is hereditary and closed under union with $K_1$.
LA - eng
UR - http://eudml.org/doc/287914
ER -

References

top
  1. Avella-Alaminos, D., Dettlaff, M., Lemańska, M., Zuazua, R., 10.7151/dmgt.1798, Discuss. Math. Graph Theory 35 (2015), 315-327. (2015) Zbl1311.05143MR3338756DOI10.7151/dmgt.1798
  2. Borowiecki, M., Broere, I., Frick, M., Mihók, P., Semanišin, G., 10.7151/dmgt.1037, Discuss. Math., Graph Theory 17 (1997), 5-50. (1997) Zbl0902.05026MR1633268DOI10.7151/dmgt.1037
  3. Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T., 10.1002/net.3230100304, Networks 10 (1980), 211-219. (1980) Zbl0447.05039MR0584887DOI10.1002/net.3230100304
  4. Cockayne, E. J., Favaron, O., Mynhardt, C. M., 10.1016/S0012-365X(03)00302-9, Discrete Math. 276 (2004), 111-125. (2004) Zbl1031.05093MR2046628DOI10.1016/S0012-365X(03)00302-9
  5. Cockayne, E. J., Hedetniemi, S. T., Independence graphs, Proc. 5th Southeast. Conf. Comb., Graph Theor., Comput., Boca Raton 1974 Utilitas Math., Winnipeg, Man. (1974), 471-491. (1974) Zbl0305.05114MR0357174
  6. Dettlaff, M., Raczek, J., Topp, J., Domination subdivision and domination multisubdivision numbers of graphs, Available at http://arxiv.org/pdf/1310.1345v2.pdf. 
  7. Favaron, O., Karami, H., Sheikholeslami, S. M., Connected domination subdivision numbers of graphs, Util. Math. 77 (2008), 101-111. (2008) Zbl1161.05055MR2462631
  8. Favaron, O., Karami, H., Sheikholeslami, S. M., 10.1007/s00373-005-0871-1, Graphs Comb. 25 (2009), 503-512. (2009) Zbl1216.05102MR2575597DOI10.1007/s00373-005-0871-1
  9. Fink, J. F., Jacobson, M. S., 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 Y. Alavi et al. (1985) Zbl0573.05050MR0812672
  10. Goddard, W., Haynes, T., Knisley, D., 10.7151/dmgt.1228, Discuss. Math., Graph Theory 24 (2004), 239-248. (2004) Zbl1065.05069MR2120566DOI10.7151/dmgt.1228
  11. Grobler, P. J. P., Critical Concepts in Domination, Independence and Irredundance of Graphs, Ph.D. Thesis, University of South Africa, ProQuest LLC (1999). (1999) MR2716892
  12. Grobler, P. J. P., Mynhardt, C. M., Upper domination parameters and edge-critical graphs, J. Comb. Math. Comb. Comput. 33 (2000), 239-251. (2000) Zbl0959.05084MR1772765
  13. Grobler, P. J. P., Mynhardt, C. M., 10.1016/S0012-365X(00)00319-8, Discrete Math. 231 (2001), 221-239. (2001) Zbl0973.05056MR1821961DOI10.1016/S0012-365X(00)00319-8
  14. Haynes, T. W., Hedetniemi, S. T., Slater, P. J., Fundamentals of Domination in Graphs, Pure and Applied Mathematics 208 Marcel Dekker, New York (1998). (1998) Zbl0890.05002MR1605684
  15. Haynes, T. W., Henning, M. A., Hopkins, L. S., 10.7151/dmgt.1244, Discuss. Math., Graph Theory 24 (2004), 457-467. (2004) Zbl1065.05070MR2120069DOI10.7151/dmgt.1244
  16. Haynes, T. W., Slater, P. J., 10.1002/(SICI)1097-0037(199810)32:3, Networks 32 (1998), 199-206. (1998) Zbl0997.05074MR1645415DOI10.1002/(SICI)1097-0037(199810)32:3
  17. Hedetniemi, S. M., Hedetniemi, S. T., Rall, D. F., 10.1016/S0012-365X(00)00012-1, Discrete Math. 222 (2000), 151-165. (2000) Zbl0961.05052MR1771395DOI10.1016/S0012-365X(00)00012-1
  18. Lemańska, M., Tey, J., Zuazua, R., Relations between edge removing and edge subdivision concerning domination number of a graph, Available at http://arxiv.org/abs/1409.7508. 
  19. Michalak, D., 10.1016/j.disc.2003.11.054, Discrete Math. 286 (2004), 141-146. (2004) Zbl1051.05069MR2084289DOI10.1016/j.disc.2003.11.054
  20. Samodivkin, V., Domination with respect to nondegenerate and hereditary properties, Math. Bohem. 133 (2008), 167-178. (2008) Zbl1199.05269MR2428312
  21. Samodivkin, V., Domination with respect to nondegenerate properties: bondage number, Australas. J. Comb. 45 (2009), 217-226. (2009) Zbl1207.05145MR2554536
  22. Samodivkin, V., Domination with respect to nondegenerate properties: vertex and edge removal, Math. Bohem. 138 (2013), 75-85. (2013) Zbl1274.05363MR3076222
  23. Samodivkin, V., 10.1007/s10587-013-0013-5, Czech. Math. J. 63 (2013), 191-204. (2013) Zbl1274.05364MR3035506DOI10.1007/s10587-013-0013-5
  24. Sampathkumar, E., Walikar, H. B., The connected domination of a graph, J. Math. Phys. Sci. 13 (1979), 607-613. (1979) Zbl0449.05057MR0575817
  25. Velammal, S., Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis, Manonmaniam Sundaranar University (1997). (1997) 

NotesEmbed ?

top

You must be logged in to post comments.