| Title:
|
Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces (English) |
| Author:
|
Samodivkin, Vladimir |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
63 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
191-204 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
domination subdivision number |
| Keyword:
|
graph property |
| Keyword:
|
bondage number |
| Keyword:
|
Roman bondage number |
| Keyword:
|
induced-hereditary property |
| Keyword:
|
orientable genus |
| Keyword:
|
non-orientable genus |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1274.05364 |
| idMR:
|
MR3035506 |
| DOI:
|
10.1007/s10587-013-0013-5 |
| . |
| Date available:
|
2013-03-01T16:15:48Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143179 |
| . |
| Reference:
|
[1] Altshuler, A.: Construction and enumeration of regular maps on the torus.Discrete Math. 4 (1973), 201-217. Zbl 0253.05117, MR 0321797, 10.1016/S0012-365X(73)80002-0 |
| Reference:
|
[2] Carlson, K., Develin, M.: On the bondage number of planar and directed graphs.Discrete Math. 306 (2006), 820-826. Zbl 1122.05045, MR 2234988, 10.1016/j.disc.2006.02.008 |
| Reference:
|
[3] Favaron, O., Haynes, T. W., Hedetniemi, S. T.: Domination subdivision numbers in graphs.Util. Math. 66 (2004), 195-209. Zbl 1071.05057, MR 2106218 |
| Reference:
|
[4] Favaron, O., Karami, H., Sheikholeslami, S. M.: Connected domination subdivision numbers of graphs.Util. Math. 77 (2008), 101-111. Zbl 1161.05055, MR 2462631 |
| Reference:
|
[5] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs.Graphs Comb. 25 (2009), 503-512. Zbl 1216.05102, MR 2575597, 10.1007/s00373-005-0871-1 |
| Reference:
|
[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 |
| Reference:
|
[7] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters.Discuss. Math., Graph Theory. 24 (2004), 239-248. Zbl 1065.05069, MR 2120566, 10.7151/dmgt.1228 |
| Reference:
|
[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 |
| Reference:
|
[9] Haynes, T. W., Henning, M. A., Hopkins, L. S.: Total domination subdivision numbers of graphs.Discuss. Math., Graph Theory 24 (2004), 457-467. Zbl 1065.05070, MR 2120069, 10.7151/dmgt.1244 |
| Reference:
|
[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. Zbl 0773.05066, MR 1206252, 10.1016/S0167-5060(08)70614-9 |
| Reference:
|
[11] Rad, N. Jafari, Volkmann, L.: Roman bondage in graphs.Discuss. Math., Graph Theory 31 (2011), 753-761. MR 2952241 |
| Reference:
|
[12] Rad, N. Jafari, Volkmann, L.: On the Roman bondage number of planar graphs.Graphs Comb. 27 (2011), 531-538. MR 2813452, 10.1007/s00373-010-0978-x |
| Reference:
|
[13] Jendrol', S., Tuhársky, M.: A Kotzig type theorem for non-orientable surfaces.Math. Slovaca 56 (2006), 245-253. Zbl 1141.05028, MR 2250077 |
| Reference:
|
[14] Kang, L., Yuan, J.: Bondage number of planar graphs.Discrete Math. 222 (2000), 191-198. Zbl 0961.05055, MR 1771398, 10.1016/S0012-365X(99)00405-7 |
| Reference:
|
[15] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties.Discrete Math. 286 (2004), 141-146. MR 2084289, 10.1016/j.disc.2003.11.054 |
| Reference:
|
[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 |
| Reference:
|
[17] Negami, S.: Classification of 6-regular Klein-bottlal graphs.Res. Rep. Inf. Sci. T.I.T. A-96 (1984). |
| Reference:
|
[18] Parsons, T. D., Pica, G., Pisanski, T., Ventre, A. G. S.: Orientably simple graphs.Math. Slovaca 37 (1987), 391-394. Zbl 0643.05027, MR 0916947 |
| Reference:
|
[19] ReVelle, C. S., Rosing, K. E.: Defendens imperium romanum: A classical problem in military strategy.Am. Math. Mon. 107 (2000), 585-594. Zbl 1039.90038, MR 1786232, 10.2307/2589113 |
| Reference:
|
[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties.Math. Bohem. 133 (2008), 167-178. Zbl 1199.05269, MR 2428312 |
| Reference:
|
[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number.Australas. J. Comb. 45 (2009), 217-226. Zbl 1207.05145, MR 2554536 |
| Reference:
|
[22] Stewart, I.: Defend the Roman Empire.Sci. Amer. 281 (1999), 136-139. 10.1038/scientificamerican1299-136 |
| Reference:
|
[23] Teschner, U.: A new upper bound for the bondage number of graphs with small domination number.Australas. J. Comb. 12 (1995), 27-35. Zbl 0839.05053, MR 1349195 |
| Reference:
|
[24] Thomassen, C.: The Jordan-Schönflies theorem and the classification of surfaces.Am. Math. Mon. 99 (1992), 116-130. Zbl 0773.57001, MR 1144352, 10.2307/2324180 |
| Reference:
|
[25] Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics.Ph.D. Thesis (1997). |
| Reference:
|
[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. Zbl 0213.26001, MR 0145512 |
| . |
