Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces

Vladimir D. Samodivkin

Czechoslovak Mathematical Journal (2013)

  • Volume: 63, Issue: 1, page 191-204
  • ISSN: 0011-4642

Abstract

top
For a graph property 𝒫 and a graph G , we define the domination subdivision number with respect to the property 𝒫 to be the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to change the domination number with respect to the property 𝒫 . In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.

How to cite

top

Samodivkin, Vladimir D.. "Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces." Czechoslovak Mathematical Journal 63.1 (2013): 191-204. <http://eudml.org/doc/252457>.

@article{Samodivkin2013,
abstract = {For a graph property $\mathcal \{P\}$ and a graph $G$, we define the domination subdivision number with respect to the property $\mathcal \{P\}$ to be the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to change the domination number with respect to the property $\mathcal \{P\}$. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.},
author = {Samodivkin, Vladimir D.},
journal = {Czechoslovak Mathematical Journal},
keywords = {domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus; domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus},
language = {eng},
number = {1},
pages = {191-204},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces},
url = {http://eudml.org/doc/252457},
volume = {63},
year = {2013},
}

TY - JOUR
AU - Samodivkin, Vladimir D.
TI - Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces
JO - Czechoslovak Mathematical Journal
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 1
SP - 191
EP - 204
AB - For a graph property $\mathcal {P}$ and a graph $G$, we define the domination subdivision number with respect to the property $\mathcal {P}$ to be the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to change the domination number with respect to the property $\mathcal {P}$. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.
LA - eng
KW - domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus; domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus
UR - http://eudml.org/doc/252457
ER -

References

top
  1. Altshuler, A., 10.1016/S0012-365X(73)80002-0, Discrete Math. 4 (1973), 201-217. (1973) Zbl0253.05117MR0321797DOI10.1016/S0012-365X(73)80002-0
  2. Carlson, K., Develin, M., 10.1016/j.disc.2006.02.008, Discrete Math. 306 (2006), 820-826. (2006) Zbl1122.05045MR2234988DOI10.1016/j.disc.2006.02.008
  3. Favaron, O., Haynes, T. W., Hedetniemi, S. T., Domination subdivision numbers in graphs, Util. Math. 66 (2004), 195-209. (2004) Zbl1071.05057MR2106218
  4. Favaron, O., Karami, H., Sheikholeslami, S. M., Connected domination subdivision numbers of graphs, Util. Math. 77 (2008), 101-111. (2008) Zbl1161.05055MR2462631
  5. 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
  6. Gagarin, A., Zverovich, V., Upper bounds for the bondage number of graphs on topological surfaces, Discrete Math. (2011), 10.1016/j.disc 2011.10.018. (2011) MR3034744
  7. Goddard, W., Haynes, T., Knisley, D., 10.7151/dmgt.1228, Discuss. Math., Graph Theory. 24 (2004), 239-248. (2004) Zbl1065.05069MR2120566DOI10.7151/dmgt.1228
  8. Haynes, T. W., Hedetniemi, S. T., Merwe, L. C. van der, Total domination subdivision numbers, J. Comb. Math. Comb. Comput. 44 (2003), 115-128. (2003) MR1962340
  9. 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
  10. Ivančo, J., 10.1016/S0167-5060(08)70614-9, Combinatorics, Graphs and Complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math 51 (1992), 113-116. (1992) Zbl0773.05066MR1206252DOI10.1016/S0167-5060(08)70614-9
  11. Rad, N. Jafari, Volkmann, L., Roman bondage in graphs, Discuss. Math., Graph Theory 31 (2011), 753-761. (2011) MR2952241
  12. Rad, N. Jafari, Volkmann, L., 10.1007/s00373-010-0978-x, Graphs Comb. 27 (2011), 531-538. (2011) MR2813452DOI10.1007/s00373-010-0978-x
  13. Jendrol', S., Tuhársky, M., A Kotzig type theorem for non-orientable surfaces, Math. Slovaca 56 (2006), 245-253. (2006) Zbl1141.05028MR2250077
  14. Kang, L., Yuan, J., 10.1016/S0012-365X(99)00405-7, Discrete Math. 222 (2000), 191-198. (2000) Zbl0961.05055MR1771398DOI10.1016/S0012-365X(99)00405-7
  15. Michalak, D., 10.1016/j.disc.2003.11.054, Discrete Math. 286 (2004), 141-146. (2004) MR2084289DOI10.1016/j.disc.2003.11.054
  16. Nakamoto, A., Negami, S., Full-symmetric embeddings of graphs on closed surfaces, Mem. Osaka Kyoiku Univ. Ser. III Nat. Sci. Appl. Sci. 49 (2000), 1-15. (2000) MR1833214
  17. Negami, S., Classification of 6-regular Klein-bottlal graphs, Res. Rep. Inf. Sci. T.I.T. A-96 (1984). (1984) 
  18. Parsons, T. D., Pica, G., Pisanski, T., Ventre, A. G. S., Orientably simple graphs, Math. Slovaca 37 (1987), 391-394. (1987) Zbl0643.05027MR0916947
  19. ReVelle, C. S., Rosing, K. E., 10.2307/2589113, Am. Math. Mon. 107 (2000), 585-594. (2000) Zbl1039.90038MR1786232DOI10.2307/2589113
  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. Stewart, I., 10.1038/scientificamerican1299-136, Sci. Amer. 281 (1999), 136-139. (1999) DOI10.1038/scientificamerican1299-136
  23. Teschner, U., A new upper bound for the bondage number of graphs with small domination number, Australas. J. Comb. 12 (1995), 27-35. (1995) Zbl0839.05053MR1349195
  24. Thomassen, C., 10.2307/2324180, Am. Math. Mon. 99 (1992), 116-130. (1992) Zbl0773.57001MR1144352DOI10.2307/2324180
  25. Velammal, S., Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (1997). (1997) 
  26. Youngs, J. W. T., Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303-315 English. Russian original translation from Kibernet. Sb., N. Ser. 7, (1970), 145-159. (1970) Zbl0213.26001MR0145512

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.