## Changing of the domination number of a graph: edge multisubdivision and edge removal.(English)Zbl 1463.05420

Summary: For a graphical property $$\mathcal{P}$$ and a graph $$G$$, a subset $$S$$ of vertices of $$G$$ is a $$\mathcal{P}$$-set if the subgraph induced by $$S$$ has the property $$\mathcal{P}$$. The domination number with respect to the property $$\mathcal{P}$$, denoted by $$\gamma_{\mathcal{P}}(G)$$, is the minimum cardinality of a dominating $$\mathcal{P}$$-set. We define the domination multisubdivision number with respect to $$\mathcal{P}$$, denoted by $$\text{msd}_{\mathcal{P}}(G)$$, as a minimum positive integer $$k$$ such that there exists an edge which must be subdivided $$k$$ times to change $$\gamma_{\mathcal{P}} (G)$$. In this paper
(a)
we present necessary and sufficient conditions for a change of $$\gamma_{\mathcal{P}}(G)$$ after subdividing an edge of $$G$$ once,
(b)
we prove that if $$e$$ is an edge of a graph $$G$$ then $$\gamma_{\mathcal{P}}(G_{e,1})<\gamma_{\mathcal{P}}(G)$$ if and only if $$\gamma_{\mathcal{P}}(G-e)<\gamma_{\mathcal{P}}(G)$$ ($$G_{e,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 $$\gamma_{\mathcal{P}}(G-e)\leq\gamma_{\mathcal{P}}(G_{e,3})\leq\gamma_{\mathcal{P}}(G-e)+1$$, and
(d)
we show that $$\text{msd}_{\mathcal{P}}(G)\leq 3$$, where $$\mathcal{P}$$ is hereditary and closed under union with $$K_1$$.

### MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: