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.
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.
A subset D of the vertex set V (G) of a graph G is called dominating in G, if each vertex of G either is in D, or is adjacent to a vertex of D. If moreover the subgraph hDi of G induced by D is regular of degree 1, then D is called an induced-paired dominating set in G. A partition of V (G), each of whose classes is an induced-paired dominating set in G, is called an induced-paired domatic partition of G. The maximum number of classes of an induced-paired domatic partition of G is the induced-paired domatic number dip(G) of G. This paper studies its properties.
Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$, if for any vertex $v \in V~- S$ there exists a vertex $u \in S$ such that $uv \in E (G)$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma (G) \le \frac{4}{11}n$.