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 ${\rm 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 \item{(a)} we present necessary and sufficient conditions for a change of $\gamma_{\mathcal{P}}(G)$ after subdividing an edge of $G$ once, \item{(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), \item{(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 \item{(d)} we show that ${\rm msd}_{\mathcal{P}}(G) \leq3$, where $\mathcal{P}$ is hereditary and closed under union with $K_1$.

Keywords

• dominating set
• edge subdivision
• domination multisubdivision number
• hereditary graph property