For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, denoted by γP (G), is the minimum cardinality of a dominating P-set. We define the domination multisubdivision number with respect to P, denoted by msdP (G), as a minimum positive integer k such that there exists an edge which must be subdivided k times to change γP (G). In this paper (a) we present necessary and sufficient conditions for a change of γP (G) after subdividing an edge of G once, (b) we prove that if e is an edge of a graph G then γP (Ge,1) < γP (G) if and only if γP (G − e) < γP (G) (Ge,t denotes the graph obtained from G by subdivision of e with t vertices), (c) we also prove that for every edge of a graph G we have γP (G − e) 6 γP (Ge,3) ≤ γP (G − e) + 1, and (d) we show that msdP (G) 6 3, where P is hereditary and closed under union with K1.
For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, is the minimum cardinality of a dominating P-set. In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate and hereditary properties when a graph is modified by adding an edge or deleting a vertex.
In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property P, denoted by γP (G), when a graph G is modified by deleting a vertex or deleting edges. A graph G is (γP (G), k)P -critical if γP (G − S) < γP (G) for any set S ( V (G) with |S| = k. Properties of (γP , k)P -critical graphs are studied. The plus bondage number with respect to the property P, denoted b + P (G), is the cardinality of the smallest set of edges U ⊆ E(G) such that γP (G − U) > γP (G). Some known results for ordinary domination and bondage numbers are extended to γP (G) and b + P (G). Conjectures concerning b + P (G) are posed.
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.