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

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.

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
Subscribers of Springer need to access the articles on their site, which is http://link.springer.com/journal/10587.


[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]