Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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
Summary:
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.
References:
[1] Altshuler, A.: Construction and enumeration of regular maps on the torus. Discrete Math. 4 (1973), 201-217. DOI 10.1016/S0012-365X(73)80002-0 | MR 0321797 | Zbl 0253.05117
[2] Carlson, K., Develin, M.: On the bondage number of planar and directed graphs. Discrete Math. 306 (2006), 820-826. DOI 10.1016/j.disc.2006.02.008 | MR 2234988 | Zbl 1122.05045
[3] Favaron, O., Haynes, T. W., Hedetniemi, S. T.: Domination subdivision numbers in graphs. Util. Math. 66 (2004), 195-209. MR 2106218 | Zbl 1071.05057
[4] Favaron, O., Karami, H., Sheikholeslami, S. M.: Connected domination subdivision numbers of graphs. Util. Math. 77 (2008), 101-111. MR 2462631 | Zbl 1161.05055
[5] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs. Graphs Comb. 25 (2009), 503-512. DOI 10.1007/s00373-005-0871-1 | MR 2575597 | Zbl 1216.05102
[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 3034744
[7] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math., Graph Theory. 24 (2004), 239-248. DOI 10.7151/dmgt.1228 | MR 2120566 | Zbl 1065.05069
[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 1962340
[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 10.7151/dmgt.1244 | MR 2120069 | Zbl 1065.05070
[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 10.1016/S0167-5060(08)70614-9 | MR 1206252 | Zbl 0773.05066
[11] Rad, N. Jafari, Volkmann, L.: Roman bondage in graphs. Discuss. Math., Graph Theory 31 (2011), 753-761. MR 2952241
[12] Rad, N. Jafari, Volkmann, L.: On the Roman bondage number of planar graphs. Graphs Comb. 27 (2011), 531-538. DOI 10.1007/s00373-010-0978-x | MR 2813452
[13] Jendrol', S., Tuhársky, M.: A Kotzig type theorem for non-orientable surfaces. Math. Slovaca 56 (2006), 245-253. MR 2250077 | Zbl 1141.05028
[14] Kang, L., Yuan, J.: Bondage number of planar graphs. Discrete Math. 222 (2000), 191-198. DOI 10.1016/S0012-365X(99)00405-7 | MR 1771398 | Zbl 0961.05055
[15] Michalak, D.: 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
[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 1833214
[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 0916947 | Zbl 0643.05027
[19] ReVelle, C. S., Rosing, K. E.: Defendens imperium romanum: A classical problem in military strategy. Am. Math. Mon. 107 (2000), 585-594. DOI 10.2307/2589113 | MR 1786232 | Zbl 1039.90038
[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. MR 2428312 | Zbl 1199.05269
[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. MR 2554536 | Zbl 1207.05145
[22] Stewart, I.: Defend the Roman Empire. Sci. Amer. 281 (1999), 136-139. DOI 10.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. MR 1349195 | Zbl 0839.05053
[24] Thomassen, C.: The Jordan-Schönflies theorem and the classification of surfaces. Am. Math. Mon. 99 (1992), 116-130. DOI 10.2307/2324180 | MR 1144352 | Zbl 0773.57001
[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 0145512 | Zbl 0213.26001
Search
Partner of
