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

Samodivkin, Vladimir

Czechoslovak Mathematical Journal, Tome 63 (2013) no. 1, pp. 191-204

Abstract (VO)

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.

Détail

DOI : 10.1007/s10587-013-0013-5

Classification : 05C69
Keywords: domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus

Bibliographie

[1] Altshuler, A.: Construction and enumeration of regular maps on the torus. Discrete Math. 4 (1973), 201-217. | DOI | MR | Zbl

[2] Carlson, K., Develin, M.: On the bondage number of planar and directed graphs. Discrete Math. 306 (2006), 820-826. | DOI | MR | Zbl

[3] Favaron, O., Haynes, T. W., Hedetniemi, S. T.: Domination subdivision numbers in graphs. Util. Math. 66 (2004), 195-209. | MR | Zbl

[4] Favaron, O., Karami, H., Sheikholeslami, S. M.: Connected domination subdivision numbers of graphs. Util. Math. 77 (2008), 101-111. | MR | Zbl

[5] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs. Graphs Comb. 25 (2009), 503-512. | DOI | MR | Zbl

[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. | MR

[7] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math., Graph Theory. 24 (2004), 239-248. | DOI | MR | Zbl

[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. | MR

[9] Haynes, T. W., Henning, M. A., Hopkins, L. S.: Total domination subdivision numbers of graphs. Discuss. Math., Graph Theory 24 (2004), 457-467. | DOI | MR | Zbl

[10] Ivančo, J.: The weight of a graph. Combinatorics, Graphs and Complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math 51 (1992), 113-116. | DOI | MR | Zbl

[11] Rad, N. Jafari, Volkmann, L.: Roman bondage in graphs. Discuss. Math., Graph Theory 31 (2011), 753-761. | MR

[12] Rad, N. Jafari, Volkmann, L.: On the Roman bondage number of planar graphs. Graphs Comb. 27 (2011), 531-538. | DOI | MR

[13] Jendrol', S., Tuhársky, M.: A Kotzig type theorem for non-orientable surfaces. Math. Slovaca 56 (2006), 245-253. | MR | Zbl

[14] Kang, L., Yuan, J.: Bondage number of planar graphs. Discrete Math. 222 (2000), 191-198. | DOI | MR | Zbl

[15] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141-146. | DOI | MR

[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. | MR

[17] Negami, S.: Classification of 6-regular Klein-bottlal graphs. Res. Rep. Inf. Sci. T.I.T. A-96 (1984).

[18] Parsons, T. D., Pica, G., Pisanski, T., Ventre, A. G. S.: Orientably simple graphs. Math. Slovaca 37 (1987), 391-394. | MR | Zbl

[19] ReVelle, C. S., Rosing, K. E.: Defendens imperium romanum: A classical problem in military strategy. Am. Math. Mon. 107 (2000), 585-594. | DOI | MR | Zbl

[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. | MR | Zbl

[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. | MR | Zbl

[22] Stewart, I.: Defend the Roman Empire. Sci. Amer. 281 (1999), 136-139. | DOI

[23] Teschner, U.: A new upper bound for the bondage number of graphs with small domination number. Australas. J. Comb. 12 (1995), 27-35. | MR | Zbl

[24] Thomassen, C.: The Jordan-Schönflies theorem and the classification of surfaces. Am. Math. Mon. 99 (1992), 116-130. | DOI | MR | Zbl

[25] Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis (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. | MR | Zbl