Changing of the domination number of a graph: edge multisubdivision and edge removal

Abstract

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 $ms{d}_{\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}$ denote the graph obtained from $G$ by subdivision of $e$ with $t$ vertices), (c) we also prove that for every edge of a graph $G$ is fulfilled ${\gamma }_{\mathcal{P}}(G-e)\le {\gamma }_{\mathcal{P}}(G_{e,3})\le {\gamma }_{\mathcal{P}}(G-e)+1$, and (d) we show that $ms{d}_{\mathcal{P}}(G)\le 3$, where $\mathcal{P}$ is hereditary and closed under union with $K_1$.

11 pages