Czechoslovak Mathematical Journal, Vol. 63, No. 1, pp. 191-204, 2013

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

Vladimir Samodivkin, UACEG, Bulgaria, Sofia, "Hristo Smirnenski" 1, Postal Code: 1146, e-mail: vlsam_fte@uacg.bg

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.

Keywords: domination subdivision number, graph property, bondage number, Roman bondage number, induced-hereditary property, orientable genus, non-orientable genus

Classification (MSC 2010): 05C69

Full text available as PDF.